#include <bits/stdc++.h>
#define Nmax 50005
#define INF 1e9
#define pi pair<int, int>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N, M;
int dist[Nmax];
bool vis[Nmax];
vector<pi> G[Nmax];
priority_queue<pi, vector<pi>, greater<pi> > Q;


void Dijsktra(int src) {
    for (int i = 1; i <= N; ++i)
        dist[i] = INF;

    dist[src] = 0;
    Q.push({0, src});
    while (!Q.empty()) {
        int node = Q.top().second;
        Q.pop();

        if (vis[node]) continue;
        vis[node] = 1;
        for (auto it: G[node]) {
            int nxt = it.first, newDist = dist[node] + it.second;
            if (!vis[nxt] && newDist < dist[nxt]) {
                 dist[nxt] = newDist;
                 Q.push(make_pair(newDist, nxt));
            }
        }
    }
}

int main()
{
    fin >> N >> M;
    while (M--) {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }

    int src = 1;
    Dijsktra(src);

    for (int i = 2; i <= N; ++i)
        if (dist[i] == INF) fout << 0 << " " ;
        else fout << dist[i] << " ";


    return 0;
}