#include<bits/stdc++.h>

#define oo 0x3f3f3f3f
#define pb push_back
#define mp make_pair

using namespace std;

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

typedef pair<int, int> Edge;
const int nmax = 50005;
vector< Edge > G[nmax];
set < Edge > h;
int N, M, dist[nmax];

void citire()
{
    f>>N>>M;

    assert(1 <= N && N <= 50000);
    assert(1 <= M && M <= 250000);

    for(int i = 1; i <= M; ++i)
    {
        int x, y, c;
        f>>x>>y>>c;

        assert(1 <= x && x <= N);
        assert(1 <= y && y <= N);
        assert(1 <= c && c <= 20000);

        G[x].pb( mp(y, c) );
    }
}

void dijkstra()
{
    memset(dist, oo, sizeof(dist));
    dist[1] = 0;
    h.insert(make_pair(0, 1)); // nod si cost
    while(!h.empty())
    {
        int node = h.begin()->second;
        int d = h.begin()->first;
        h.erase(h.begin());

        for(vector< Edge >::iterator it = G[node].begin(); it != G[node].end(); ++it)
        {
            int to = it->first;
            int cost = it->second;
            if( dist[to] > dist[node] + cost )
            {
                if(dist[to] != oo)
                    h.erase(h.find(make_pair(dist[to], to)));
                dist[to] = dist[node] + cost;
                h.insert(make_pair(dist[to], to));
            }

        }

    }

    for(int i = 2; i <= N; ++i){
        if(dist[i] == oo)
            dist[i] = 0;
        g<<dist[i]<<" ";
    }
}

int main()
{
    citire();
    dijkstra();
    return 0;
}