#include<bits/stdc++.h>

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

using namespace std;

FILE *in = fopen("dijkstra.in", "r"), *out = fopen("dijkstra.out", "w");
typedef pair<int, int> Edge;
const int nmax = 5e4+5;
vector< Edge > G[nmax];
set < Edge > h;
int N, M, dist[nmax];

void citire()
{
    fscanf(in, "%d%d", &N, &M);

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

    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        fscanf(in, "%d%d%d", &x, &y, &c);

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

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

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

        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(to, dist[to])));
                dist[to] = dist[node] + cost;
                h.insert(make_pair(to, dist[to]));
            }
        }
    }

    for(int i = 2; i <= N; i++)
        fprintf(out, "%d ", dist[i]);
}

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