#include <bits/stdc++.h>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int N = 50005;
const int INF = 1e9;
#define PII pair<int,int>
vector<PII> v[N];
int dist[N];
priority_queue<PII, vector<PII>, greater< PII > >q;

int main()
{
    int n,m;
    in >> n >> m;
    for (int i = 1; i<=m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        v[x].push_back({y,c});
    }
    for (int i = 2; i<=n; i++)
        dist[i] = INF;
    q.push({0,1});
    while (!q.empty())
    {
        int now = q.top().second,cost = q.top().first;
        q.pop();
        if (dist[now]!=cost)
            continue;
        for (auto it: v[now])
            if (dist[it.first]>dist[now]+it.second)
            {
                dist[it.first] = dist[now]+it.second;
                q.push({dist[it.first],it.first});
            }
    }
    for (int i = 2; i<=n; i++)
        if (dist[i] == INF)
            out << "0 ";
        else
            out << dist[i] << " ";
}