#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define inf 1000000

int n,m,x,y, a[5005][5005], d[50005], t[50005], i, c,j, Min, Max;
bool sel[50005];

void load()
{
    f >> n >> m;
    Max=0;
    for ( i=1; i <= n; ++i)
        for( j=1; j <= n; ++j)
            if(i!=j) a[i][j] = inf; else a[i][j] = 0;

    for (i=1 ; i<=m; ++i)
    {
        f>> x >> y >> c;
        a[x][y]=c;
 //       if( c > Max) Max=c;
    }

}

void dij()
{
    int k;
    for(i=1; i<=n; i++)
    {
        t[i]=0;
        d[i]=inf;
        sel[i]=false;
    }
    d[1]=0;

    for(i=1; i <= n; i++)
    {
        Min=inf;

        for( j=1; j <= n; j++ )
            if( d[j] < Min && !sel[j] )
            {
                Min=d[j];
                k=j;
            }

        sel[k] = true;
        for (j = 1 ; j <= n; j++)
            if( d[j] > d[k] + a[k][j] && !sel[j])
            {
                d[j] = d[k] + a[k][j];
                t[j]=k;
            }
    }
}

int main()
{
    load();
    dij();

    for(i=2; i<=n; ++i)
        g<<d[i]<<" ";

    return 0;
}