#include <stdio.h>
#include <vector>

#define MAXN 50010
#define INF 1000000000
#include <fstream>

using namespace std;
 
int d[MAXN];
int N,M;
vector<int> C[MAXN], G[MAXN];
int Q[1<<20];
 

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void init()
{  
    int i;
    for(i=2;i<=N;i++)
        d[i]=INF;
}
 
void citire()
{
    
    fin>>N>>M;
 
    int i,j,t,z;
 
    for(z=1;z<=M;z++)
    {  
        fin>>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;
       
    for(i=2;i<=N;i++)
	{
		if(d[i]==INF) d[i]=0;
		fout<<d[i]<<" ";
	}
 
     
}
 
int main()
{
    citire();
    init();
    bell();
    afisare();
}