/**friendly reminder: NU puneti INT_MAX ca inf, pentru ca va va da overflow cand il bagati in heap*/
#include <bits/stdc++.h>
#define MOD 1999999973
#define ull unsigned long long

using namespace std;

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

vector<pair<int,int>> G[50005];
priority_queue<pair<int,int>> Q;
int val[50005];
int viz[50005];
int n,m;

int findmin(){
    int sol;
    while(viz[Q.top().second] == 1){
        Q.pop();
    }
    sol = Q.top().second;
    Q.pop();
    return sol;
}

void Dijkstra(){
    int i,j,vecin,cost,minim;
    Q.push(make_pair(0,1));
    for(i = 2; i <= n; ++i){
        val[i] = 1000001;
        Q.push(make_pair(-val[i],i));
    }
    for(i = 1; i <= n; ++i){
        minim = findmin();
        viz[minim] = 1;
        for(j = 0; j < G[minim].size(); j++){
            vecin = G[minim][j].first;
            cost = G[minim][j].second;
            if(val[vecin] > val[minim] + cost){
                val[vecin] = val[minim] + cost;
                Q.push(make_pair(-val[vecin],vecin));
            }
        }
    }
}

int main()
{
    int i,j,a1,a2,c1;
    fin>>n>>m;
    for(i = 1; i <= m; ++i){
        fin>>a1>>a2>>c1;
        G[a1].push_back(make_pair(a2,c1));
    }
    Dijkstra();
    for(i = 2; i <= n; i++){
        if(val[i] == 1000001){
            fout<<"0 ";
        }else
            fout<<val[i]<<' ';
    }
    return 0;
}