#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 50010
#define INF 1000000000
 
int d[MAXN];
int N,M;
vector<int> C[MAXN], G[MAXN];
int Q[1<<20];
 
void init()
{  
    int i;
    for(i=2;i<=N;i++)
        d[i]=INF;
}
 
void citire()
{
    FILE *fin=fopen("dijkstra.in","r");
    fscanf(fin,"%d %d",&N,&M);
 
    int i,j,t,z;
 
    for(z=1;z<=M;z++)
    {  
        fscanf(fin,"%d %d %d",&i,&j,&t);
        G[i].push_back(j);
        C[i].push_back(t);
 
    }
     
}
 
int bell()
{
    unsigned int x,i;
    int inc, sf;
    inc = sf = 0;
    Q[0] = 1;
    while(inc<=sf)
    {  
        x = Q[inc];
        inc++;
        for(i=0;i<G[x].size();i++)
            if(d[G[x][i]]>d[x]+C[x][i])
				{
				d[G[x][i]]=d[x]+C[x][i];
				sf++; 
				Q[sf] = G[x][i];
				}  
             
    }  
return 0;    
}
 
void afisare()
{
    int i;
    FILE *fout=fopen("dijkstra.out","w");
     
     
    for(i=2;i<=N;i++)
	{
		if(d[i]==INF) d[i]=0;
		fprintf(fout,"%d ",d[i]);
	}
 
     
}
 
int main()
{
    citire();
    init();
    bell();
    afisare();
	     
return 0;
}