#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const string file = "dijkstra";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, nmax = 50005;

int n, m, d[nmax];
priority_queue<pi> q;
vector<pi> v[nmax];

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y, z;
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    for (int i = 2; i <= n; ++i)
        d[i] = inf;
    q.push({0, 1});
    while(!q.empty()){
        int nod = q.top().ss, cost = -q.top().ff;
        q.pop();
        if(cost != d[nod])
            continue;
        for (auto x : v[nod])
            if(d[x.ff] > d[nod]+x.ss){
                d[x.ff] = d[nod] + x.ss;
                q.push({-d[x.ff], x.ff});
            }
    }
    for (int i = 2; i <= n; ++i)
        fout << (d[i] == inf ? 0 : d[i]) << " ";
    return 0;
}