#include<cstdio>
#include<cstdlib>
using namespace std;
int n,m;
int *g[50001],*cost[50001],deg[50001],d[50001],q[50001],a,b,c;
const int inf = 1 << 30; 
void dijkstra()
{for(int i=1;i<n;i++)
 d[i]=inf;
 int pmin=0,min;
 for(int i=0;i<n;i++)
 {min=inf;
 for(int j=1;j<n;j++)
  if(d[j]<min && !q[j]) {min=d[j];pmin=j;}
   q[pmin]=1;  
   int * t=g[pmin],*c1=cost[pmin];
   while(*t!=-1)
    {if(d[*t]>d[pmin]+*c1) d[*t]=d[pmin]+*c1;t++;c1++;} }
     
     }
int main()
{freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d %d",&n,&m);
for(;m;m--)
{scanf("%d %d %d",&a,&b,&c);a--;b--;
deg[a]++;}
for(int i=0;i<n;deg[i++]=0)
{g[i]=(int *)malloc(deg[i]*sizeof(int));
cost[i]=(int *)malloc(deg[i]*sizeof(int)); }
fseek(stdin,0,SEEK_SET);
scanf("%d %d",&n,&m);
for(;m;m--)
{scanf("%d %d %d",&a,&b,&c);
 a--;b--;g[a][deg[a]]=b;cost[a][deg[a]++]=c;}
for(int i=0;i<n;i++)
{g[i][deg[i]]=-1;
}
for(int i=1;i<n;i++)
 d[i]=inf;
for(int i=0;i<deg[0];i++)
d[g[0][i]]=cost[0][i]; 
dijkstra();
for(int i=1;i<n;i++) printf("%d ",d[i]);
return 0;
    
    }