#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "string.h"
#include "memory.h"

#define MAX 50
#define MAXSTRL 200
#define MAXISM 99999

typedef struct Node{ //結點
  int vertex;
  int weight;
  struct Node *next;
} Node;

typedef struct {//堆
	 Node * start[MAX+1];
} Graph;

Graph stack;//定義堆

int Adj[MAX+1][MAX+1];  //鄰接矩陣　

int vexnum,edgnum;//結點和邊數目　
int heapleftnum; //堆中剩佘的結點數
int sum=0;       //放和的地方
char result[MAXSTRL];//放結果和臨時字串
char temp[MAXSTRL];
char * str=result;


void Adjut(int p)//對堆，從節點p為根節點的樹調整成堆，堆的節點數為heapleftnum
{   
	int work,temp;
	Node * temppoint;
	work=p; //工作變量
	temp=work *2;

	while(temp<=heapleftnum)
	{
		if ( (temp<heapleftnum) && ( (stack.start[temp]->weight)>(stack.start[temp+1]->weight) ) ) //臨時節點有右鄰且右鄰權小于臨時節點
		    temp++;//臨時節點指向小的
		if (stack.start[temp]->weight>=stack.start[work]->weight)  //臨時節點比工作節點權大
			break;//結束排序，
			
		work=temp;	//臨時節點比工作節點權小,當前工作結點改為臨時節點
		temp=temp*2;	
	}
  	
	if (p!=work) //交換
	 { temppoint=stack.start[p];
	 stack.start[p]=stack.start[work];
	 stack.start[work]=temppoint;
	 }
}

void Heap_sort() //heap sort
{
	int work=(int)(heapleftnum/2);//堆排序工作變量，指向最后一個要排序的堆節點
	while (work>0)           //對從vexnum/2開始到1的節點進行堆基本排序
	 {Adjut(work);work--;}
}


int removeMin() //返回第一個堆節點的號，將第一個堆節點與最后一個節點對換，
{ Node * t;
  t=stack.start[1];
  stack.start[1]=stack.start[heapleftnum];
  stack.start[heapleftnum]=t;
  return (heapleftnum);
}


void main()  //main prostackm
{ 
   int x,y,num,i,j,r,u,t1,t2,t;
   printf("mst\n");
   scanf("%d %d",&vexnum,&edgnum);
 
   //初始化鄰接矩陣
   for (i=1;i<=vexnum;i++)
   {
	   for (j=1;j<=vexnum;j++)
		   Adj[i][j]=MAXISM;
   }
   //建立鄰接矩陣
   for (i=1;i<=edgnum;i++)
   {
     scanf(" %d %d %d", &x,&y,&num);
     Adj[x][y]=num;
	 Adj[y][x]=num;
   }

   //分配堆空間，初始化堆
   for (i=1;i<=vexnum;i++)
     {stack.start[i]=(Node *)malloc(sizeof(Node));
      stack.start[i]->vertex=i;
	  if (i==1) stack.start[i]->weight=0;
	  else stack.start[i]->weight=MAXISM;
      stack.start[i]->next=NULL;
	  }

   heapleftnum=vexnum;//記錄剩余的節點個數

   Heap_sort();//把stack第一次變成堆

   while (heapleftnum!=0)
   { u=removeMin();   //就是把Q中頂端的值彈出付給u,u是堆的序號，不是圖的節 點號， 然后再把"堆"中最后一個值放到頂端，
	 heapleftnum--;
     Heap_sort();//然后平衡這個堆
     for (i=1;i<=heapleftnum;i++) 
     if (Adj[stack.start[u]->vertex][stack.start[i]->vertex]!=MAXISM)    //對圖G中與u相臨的所有邊
	   {r=Adj[stack.start[u]->vertex][stack.start[i]->vertex];  //stack[i]->vertex是邊e的另一頭頂點,r是邊e的權值
	   if (r<=(stack.start[i]->weight))  //意思是r 比堆中的i的權小，i的距離就是開始時設的∞
	     if ((r==stack.start[i]->weight) && (stack.start[u]->vertex>stack.start[i]->next->vertex)) {}//如果距里相同，且當前結點序號stack.start[u]->vertex大于結點stack.start[i]->vertex原來指向的結點號stack.start[i]->next->vertex則原連接不變
		 else
		 { stack.start[i]->weight=r;   //把r付給stack.start[i]的權值
           stack.start[i]->next=stack.start[u];    //就是i指向stack.start[u]
	       Heap_sort();                            //然后再平衡一遍這個堆
	     }
	 }
  }

  //輸出結果
   for( i=vexnum;i>0;i--)
   {
	    if(stack.start[i]->next!=NULL)
		{
		 t1=stack.start[i]->vertex;
		 t2=stack.start[i]->next->vertex;
		 if(t1>t2)
		 {
			t=t1;
			t1=t2;
			t2=t;
		 } 
	     sprintf(temp,"%d %d %d\n",t1,t2,Adj[t1][t2]);
         str=strcat(str,temp);
	     sum+=Adj[t1][t2];
		}
   }
 

 printf("Cost:%d\n%s",sum,result); 
  //回收堆空間
   for (i=1;i<=vexnum;i++)
     free(stack.start[i]); 
}




/*
while (Q!=空)
{
   u=removeMin(Q);//就是把Q中頂端的值彈出付給u, 然后再把"堆"中最后一個值放到頂端，然后平衡這個堆
   for all e屬于 G.incidentEdge(u); 
          // e是圖G中與u相臨的所有邊
   {
      z=G.opposite (u,e) ; //z是邊e的另一頭頂點
      r=weight(e); //r是邊e的權值
      if (r<getdistance(z))  //意思是r 比堆中的z的權小，z的距離就是開始時設的∞。
	  {setdistance(z,r); //把r的權值付給z,
        setparent(u,z);  //就是z的另一頂點設為u,開始時都為Null
        //然后再平衡一遍這個堆；
	  }
   }
}
*/