#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,pozitie=10004;
vector <int> G[MAXN],C[MAXN];
set < pair<int, int> > T;
char buff[10005];

void citire(int &nr){
    nr=0;
    while(buff[pozitie]<'0' || buff[pozitie]>'9')
        if (++pozitie==10005){
            fread (buff,1,10005,stdin);
            pozitie=0;
        }
    while('0'<=buff[pozitie] && buff[pozitie]<='9'){
        nr=nr*10+buff[pozitie]-'0';
        if (++pozitie==10005){
            fread (buff,1,10005,stdin);
            pozitie=0;
        }
     }
}

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

    citire(N);
    citire(M);

    for (i=1;i<=M;i++)
    {
        citire(a);
        citire(b);
        citire(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;
}