#include <bits/stdc++.h>

using namespace std;

ifstream F("dijkstra.in");
ofstream G("dijkstra.out");

const int inf = 1 << 30;
int d[50005], z[50005], x, y, c, p, n, m, a;
vector <pair<int, int> > graf[50005];
priority_queue <pair<int, int> > pq;

int main()
{
    F >> n >> m;
    p = 1;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y >> c;
        graf[x].push_back({y, c});
    }
    for(int i = 1; i <= n; ++ i)
        d[i] = inf;
    d[p] = 0;
    pq.push({0, p});
    while(!pq.empty())
    {
        a = pq.top().second;
        pq.pop();
        if(z[a]) continue;
        z[a] = 1;
        for(auto i : graf[a])
        {
            if(d[a] + i.second < d[i.first])
            {
                d[i.first] = d[a] + i.second;
                pq.push({-d[i.first], i.first});
            }
        }
    }
    for(int i = 2; i <= n; ++ i)
        d[i] == inf ? G << "0 " : G << d[i] << " ";
    return 0;
}