#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000000
//有向圖 
int main(){
  int n,m,a,b,v,i,j,min,k;
  scanf("%d%d",&n,&m);//輸入n個(gè)頂點(diǎn)，m條邊 
  int g[n+1][n+1],d[n+1],vis[n+1];//g[i][j]表示i到j(luò)的邊的權(quán)值,vis[i]表示到此頂點(diǎn)的最短路是否已經(jīng)找到，d[i]當(dāng)前源點(diǎn)到i頂點(diǎn)的最短路徑 
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++){ 
    for(j=0;j<=n;j++){
      g[i][j]=max;
    }
    d[i]=max;  
  }
  for(i=0;i<m;i++){//i到j(luò)的邊權(quán)值儲(chǔ)存到g鄰接矩陣中,i點(diǎn)到j(luò)點(diǎn)無直接相連的邊時(shí)，g[i][j]=max 
    scanf("%d%d%d",&a,&b,&v);
    g[a][b]=v;
  }
  for(i=2;i<=n;i++){
      d[i]=g[1][i]; //初始化源點(diǎn)到i點(diǎn)邊權(quán)值，之后過程中會(huì)發(fā)生變化 
  }
  vis[1]=1;
  for(i=2;i<=n;i++){//共循環(huán)n-1次，每循環(huán)一次，確定一條最短路，再次循環(huán)時(shí)這條路就不用考慮了，去尋找下一條最短路 
    min=max;
    for(j=2;j<=n;j++){//尋找下一條當(dāng)前最短路 
      if(d[j]<min&&vis[j]==0){
       min=d[j];
       k=j;
      }  
    }
    vis[k]=1;//找到了，到k點(diǎn)的路是當(dāng)前最短路，標(biāo)記它，根據(jù)它尋找下一條最短路 
    for(j=2;j<=n;j++){
      if(d[j]>d[k]+g[k][j]&&vis[j]==0){//經(jīng)過此k點(diǎn)到達(dá)j點(diǎn)的路徑是否小于其他到達(dá)j點(diǎn)的路徑 
        d[j]=d[k]+g[k][j];
      }
    }
  }  
  for(i=2;i<=n;i++){//輸出到達(dá)個(gè)點(diǎn)的最短路徑 
    printf("%d\n",d[i]);
  }
  return 0;
}

#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000000
typedef struct{ 
  int d;//到達(dá)某點(diǎn)的最短路徑距離 
  int pre;//該最短路徑是經(jīng)過哪個(gè)點(diǎn)傳過來的，源點(diǎn)或其他某個(gè)點(diǎn) 
}path;
//有向圖 
int main(){
  int n,m,a,b,v,i,j,min,k,from;
  scanf("%d%d",&n,&m);//輸入n個(gè)頂點(diǎn)，m條邊 
  int g[n+1][n+1],vis[n+1];//g[i][j]表示i到j(luò)的邊的權(quán)值,vis[i]表示到此頂點(diǎn)的最短路是否已經(jīng)找到，d[i]當(dāng)前源點(diǎn)到i頂點(diǎn)的最短路徑 
  path to[n+1];//記錄當(dāng)前到某個(gè)點(diǎn)的最短路徑以及從哪個(gè)點(diǎn)傳過來的 
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++){ 
    for(j=0;j<=n;j++){
      g[i][j]=max;
    }
    to[i].d=max;  
  }
  for(i=0;i<m;i++){//i到j(luò)的邊權(quán)值儲(chǔ)存到g數(shù)組中,i點(diǎn)到j(luò)點(diǎn)無直接相連的邊時(shí)，g[i][j]=max 
    scanf("%d%d%d",&a,&b,&v);
    g[a][b]=v;
    g[b][a]=v;
  }
  for(i=2;i<=n;i++){
      to[i].d=g[1][i]; //初始化源點(diǎn)到i點(diǎn)邊權(quán)值，之后過程中會(huì)發(fā)生變化 
      if(g[1][i]!=max){
       to[i].pre=1; 
      } 
  }
  vis[1]=1;
  for(i=2;i<=n;i++){//共循環(huán)n-1次，每循環(huán)一次，確定一條最短路，再次循環(huán)時(shí)這條路就不用考慮了，去尋找下一條最短路 
    min=max;
    for(j=2;j<=n;j++){//尋找下一條當(dāng)前最短路 
      if(to[j].d<min&&vis[j]==0){
       min=to[j].d;
       k=j;
      }  
    }
    vis[k]=1;//找到了，到k點(diǎn)的路是當(dāng)前最短路，標(biāo)記它，根據(jù)它尋找下一條最短路 
    for(j=2;j<=n;j++){
      if(to[j].d>to[k].d+g[k][j]&&vis[j]==0){//經(jīng)過此k點(diǎn)到達(dá)j點(diǎn)的路徑是否小于其他到達(dá)j點(diǎn)的路徑 
        to[j].d=to[k].d+g[k][j];
        to[j].pre=k;//改變j點(diǎn)是誰(shuí)傳來的，現(xiàn)在到j(luò)點(diǎn)的最短路徑是經(jīng)過k點(diǎn)的，由j點(diǎn)傳來 
      }
    }
  }  
  for(i=2;i<=n;i++){//輸出到達(dá)個(gè)點(diǎn)的最短路徑 
    printf("%d ",to[i].d);
    printf("%d ",i);
    j=i;
    while(j!=1){
      j=to[j].pre;
      printf("%d ",j);
    }
    printf("\n");
  }
  return 0;
}