#include <cstdio>
#include <vector>
#include <utility>
#define pb push_back
#define INF 200000000
#define Nr 50001
using namespace std;

int N, M, H[Nr], T[Nr], D[Nr], P[Nr];
vector< pair< int, int > > G[Nr];

inline void read()
{
    int i,x,y,cost;
    for (i=1; i<=M; i++)
    {
        scanf("%d%d%d", &x, &y, &cost);
        G[x].pb( make_pair(y, cost) );
        // G[y].pb( make_pair(x, cost) );
    }
}

inline void swap(int i, int j)
{
    int x;
    x=H[i],H[i]=H[j],H[j]=x;
    x=P[H[i]],P[H[i]]=P[H[j]],P[H[j]]=x;
}

inline void HeapUp(int i)
{
    if (D[H[i]]>D[H[i/2]]) return;
    swap(i, i/2);
    HeapUp(i/2);
}

inline void HeapDown(int i)
{
    int st,dr;
    if (i*2>M) return;
    st=D[H[i*2]];
    if (i*2+1>M) dr=st+1; else dr=D[H[i*2+1]];
    if (st<dr)
    {
        if (D[H[i]]<st || st==INF) return;
        swap(i, i*2);
        HeapDown(i*2);
    }
    else
    {
        if (D[H[i]]<dr || dr==INF) return;
        swap(i, i*2+1);
        HeapDown(i*2+1);
    }
}

inline void initialize()
{
    M=N;
    for (int i=1; i<=N; i++)
    {
        D[i]=INF;
        H[i]=i;
        P[i]=i;
    }
    D[1]=0;
    D[0]=-1;
}

inline void solve()
{
    int i, nod;
    vector< pair< int, int > >::iterator it;
    for (i=1; i<=N; i++)
    {
        nod=H[1];
        swap(1, M);
        M--;
        HeapDown(1);
        for (it=G[nod].begin(); it!=G[nod].end(); it++)
            if (D[(*it).first]> D[nod] + (*it).second)
            {
                D[(*it).first]= D[nod] + (*it).second;
                T[(*it).first]=nod;
                HeapUp( P[(*it).first] );
            }
    }
}

inline void afis()
{
    int i;
    for (i=2; i<=N; i++) if (D[i]==INF) D[i]=0;
    for (i=2; i<=N; i++)
        printf("%d ", D[i]);
}
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &N, &M);
    read();
    initialize();
    solve();
    afis();
    return 0;
}