#include <cstdio>
#include <set>
#include <vector>

using namespace std;

const int MAXN=50100;
const int INF=1000000000;

int N,M,d[MAXN],i,j,k,val,x,a,b,c;
vector <int> G[MAXN],C[MAXN];
set < pair<int, int> > T;

int main()
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    scanf("%d %d\n", &N, &M);

    for (i=1;i<=M;i++)
    {
        scanf("%d %d %d\n", &a, &b, &c);
        G[a].push_back(b);
        C[a].push_back(c);
    }

    for (i=2;i<=N;i++)
        d[i]=INF;

    T.insert(make_pair(0, 1));

    while (T.size()>0)
    {
        val=(*T.begin()).first;
        x=(*T.begin()).second;
        T.erase(*T.begin());
        for(i=0;i<G[x].size();i++)
            if (d[G[x][i]]>val+C[x][i])
            {
                d[G[x][i]]=val+C[x][i];
                T.insert(make_pair(d[G[x][i]],G[x][i]));
            }
    }

    for (i=2;i<=N;i++)
        printf("%d ", d[i]==INF ? 0 : d[i]);

    return 0;
}