#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
typedef pair<int, int> Pair;
#define MAXN 50005
#define INF (int)2e9
#define v second
#define c first
int n, m, D[MAXN];
bool InQ[MAXN];
vector<Pair> G[MAXN];
queue<Pair> Q;

void solve() {
    for(int i=0; i<=n; ++i)
        D[i]=INF;
    D[1]=0, Q.push(Pair(0,1)), InQ[1]=1;
    while(!Q.empty()){
        int node=Q.front().v; Q.pop();
        InQ[node]=0;
        for(auto &e : G[node])
            if(D[e.v] > D[node] + e.c) {
                D[e.v]=D[node]+e.c;
                if(!InQ[e.v]){
                    Q.push(make_pair(D[e.v], e.v));
                    InQ[e.v]=1;
                }
            }
    }
}

int main() {
    int a, b, x;
    fin>>n>>m;
    while(m--) {
        fin>>a>>b>>x;
        G[a].push_back(Pair(x, b));
    }
    solve();
    for(int i=2; i<=n; ++i)
        if(D[i] < INF)
            fout<<D[i]<<" ";
        else
            fout<<"0 ";
    return 0;
}