#include <bits/stdc++.h>

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n, m, x;
struct nod{
    int p, c;
    bool operator < (const nod &A) const{
        return c > A.c;
    }
};
nod aux1, aux2;
vector <nod> v[50005];
int d[50005];
queue <nod> q;

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> x >> aux1.p >> aux1.c;
        v[x].push_back(aux1);
    }
    for(int i = 1; i <= n; i++){
        d[i] = -1;
    }
    aux1.p = 1;
    aux1.c = 0;
    d[1] = 0;
    q.push(aux1);
    while(!q.empty()){
        aux1 = q.front();
        if(aux1.c > d[aux1.p] && d[aux1.p] != -1){
            q.pop();
            continue;
        }
        for(int i = 0; i < v[aux1.p].size(); i++){
            if(d[v[aux1.p][i].p] == -1 || d[v[aux1.p][i].p] > d[aux1.p] + v[aux1.p][i].c){
                aux2.p = v[aux1.p][i].p;
                d[v[aux1.p][i].p] = d[aux1.p] + v[aux1.p][i].c;
                aux2.c = d[v[aux1.p][i].p];
                q.push(aux2);
            }
        }
        q.pop();
    }
    for(int i = 2; i <= n; i++){
        if(d[i] == -1){
            fout << 0 << " ";
        }
        else{
            fout << d[i] << " ";
        }
    }
    return 0;
}