#include <bits/stdc++.h>
#define Nmax 50005
#define INF 2e9
using namespace std;

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

int N, M;
int dp[Nmax];
bool vis[Nmax];
vector<pair<int, int> > G[Nmax];

struct elem{
    int node, dist;
    bool operator <(const elem &x) const
    {
        return dist > x.dist;
    }
};
priority_queue<elem> Q;
int main()
{
    fin >> N >> M;
    while (M--) {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back({y, c});
    }

    for (int i = 2; i <= N; ++i)
        dp[i] = INF;

    Q.push({1, 0});
    while (!Q.empty()) {
        int node = Q.top().node, dist = Q.top().dist;
        Q.pop();
        if (vis[node]) continue;
        vis[node] = 1;
        for (auto it: G[node]) {
            int nxt = it.first, len = it.second + dist;
            if (len >= dp[nxt]) continue;
            dp[nxt] = len;
            Q.push({nxt, len});
        }
    }

    for (int i = 2; i <= N; ++i)
        fout << dp[i] << " ";

    return 0;
}