#include<fstream>
#include<iostream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
long long inf=2000000000;
long n,m,start;
struct muchie
{
long x,y,c;
} a[250001];

long d[50001];

int main()
{
    long i;
    f>>n>>m; //>>start;
    start=1;
    for( i=1;i<=m;i++ )
    {
        f>>a[i].x>>a[i].y>>a[i].c;
        if(a[i].x==start) d[a[i].y]=a[i].c;
        if(a[i].y==start) d[a[i].x]=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;
            }
           /* else
            if(d[a[i].x]>d[a[i].y]+a[i].c)
            {
                gata=0;
                d[a[i].x]=d[a[i].y]+a[i].c;
            }
            */
    }
    for( i=1;i<=n;i++ )
        if (i!=start)
        {
                  if(d[i]>=32000 || i==start)  g<<"0 ";
                                       else    g<<d[i]<<" ";
        }

    f.close();g.close();
    return 0;
}