#include <stdio.h>
#include <stdlib.h>
#define nume "dijkstra"
#define oo 0x3f3f3f3f
const int maxn=50001;
 

FILE *in=fopen(nume".in","r"),*out=fopen(nume".out","w");

struct graf{
  int a,c;
};

int *g[maxn],*c[maxn];
int n,m,d[maxn],q[300000],s,dest,u[maxn];

void citire(){
  int i,a,b,cost;
  fscanf(in,"%d%d",&n,&m);
  for(i=1;i<=n;i++){
    g[i]=(int*)realloc(g[i],sizeof(int));
    c[i]=(int*)realloc(c[i],sizeof(int));
    g[i][0]=0;
    c[i][0]=0;
  }
  for(i=1;i<=m;i++){
    fscanf(in,"%d%d%d",&a,&b,&cost);
    g[a][0]++;
    g[a]=(int*)realloc(g[a],sizeof(int)*(g[a][0]+1));
    g[a][g[a][0]]=b;

    c[a]=(int*)realloc(c[a],sizeof(int)*(g[a][0]+1));
    c[a][g[a][0]]=cost;
    
  }
}

void bellman(){
  int i,l,k,j,y;
  s=1;dest=n;
  for(i=1;i<=n;i++)d[i]=oo;
  l=1;
  q[l]=s;
  u[s]=1;
  d[s]=0;
  for(i=1;i<=l;i++){
    k=q[i];
    for(j=1;j<=g[k][0];j++){
      y=g[k][j];
      if(d[y]>d[k]+c[k][j])d[y]=d[k]+c[k][j];
      if(!u[y]){
	q[++l]=y;
	printf("(%d)",l);
	u[y]=1;
      }
    }
    // u[k]=0;
  }
  
}




int main(){

   citire();
   bellman();
  for ( int i = 2; i <= n; ++i )  
    fprintf(out, "%d ", d[i] == oo ? 0 : d[i]);       fprintf(out, "\n");  
  
  fclose(in);
  fclose(out);
  return 0;
}