#include<fstream>
#include<iostream>
using namespace std;
 
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
using namespace std;
long n,m;
struct muchie {long x,y,c;} a[250001];
long d[50001];
int main()
{      
    long i;
    f>>n>>m;
    for( i=1;i<=m;i++ )
    { 
        f>>a[i].x>>a[i].y>>a[i].c;
        if(a[i].x==1) 
            d[a[i].y]=a[i].c; 
    }   
 
    for( i=1;i<=n;i++) 
        if(d[i]==0) 
            d[i]=250001; 
           
    int gata=0;
    while(!gata)
    {
        gata=1;
        for( int i=1; i<=m; i++ )
                if(d[a[i].y]>d[a[i].x]+a[i].c)
            { 
                gata=0;
                d[a[i].y]=d[a[i].x]+a[i].c;
            }
    } 
    for( i=2;i<=n;i++ )
        if( d[i]>=32000 ) 
            g<<"0 ";
        else
            g<<d[i]<<" ";
    return 0;
}