#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define MAXN 50005
#define INF (int)2e9
struct Edge{
    int v, c;
    Edge(int a, int b){
        v=a, c=b;
    }
};
int n, m, D[MAXN];
bool InQ[MAXN];
vector<Edge> G[MAXN];
queue<int> Q;

void solve() {
    int cnt=0;
    for(int i=0; i<=n; ++i)
        D[i]=INF;
    D[1]=0, Q.push(1), InQ[1]=1;
    while(!Q.empty()){
        int node=Q.front(); 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(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(Edge(b, x));
    }
    solve();
    for(int i=2; i<=n; ++i)
        if(D[i] < INF)
            fout<<D[i]<<" ";
        else
            fout<<"0 ";
    return 0;
}