#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
const int Nmax = 50005;
const int INF  = 0x3f3f3f3f;

typedef pair<int, int> pii;
vector<pii> G[Nmax];
priority_queue<pii, vector<pii>, greater<pii> > PQ;
int used[Nmax];
int dist[Nmax];

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

    int N, M, a, b, w;
    f >> N >> M;
    for (int e = 0; e < M; e++) {
        f >> a >> b >> w;
        G[a-1].push_back(make_pair(b-1, w));
    }
    memset(used, 0, sizeof(used));
    memset(dist, INF, sizeof(dist));

    dist[0] = 0;
    used[0] = 1;

    for (int i = 0; i < G[0].size(); i++) {
        PQ.push(make_pair(G[0][i].second, G[0][i].first));
    }

    while (!PQ.empty()) {
        pii P = PQ.top(); PQ.pop();
        if (!used[P.second]) {
            int d = P.first;
            a = P.second;
            used[a] = 1;
            dist[a] = d;
            for (int i = 0; i < G[a].size(); i++) {
                if (!used[G[a][i].first]) {
                    b = G[a][i].first;
                    if (dist[b] > dist[a] + G[a][i].second)
                        dist[b] = dist[a] + G[a][i].second;
                    PQ.push(make_pair(dist[b], b));
                }
            }
        }
    }
    for (int i = 1; i < N; i++)
        g << (dist[i] != INF ? dist[i] : 0) << ' ';
    g << '\n'; 

    return 0;
}