#include <bits/stdc++.h>

using namespace  std;
const int nmax = 50005;
const int MOD = 1e9+7;

int x,y,w,m,n;
int main(){
//    freopen("dijkstra.in","r",stdin);
//    freopen("dijkstra.out","w",stdout);
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    vector<pair<int,int>> G[n+1];
    for(int i=1;i<=m;i++){
        fin>>x>>y>>w;
        G[x].push_back({y,w});
    }
    priority_queue<pair<int,int>> Q;
    vector<int> d(n+1,1e9);
    bitset<nmax> vis;
    d[1]=0;
    Q.push({0,1});
    while(!Q.empty()){
        int dist = -Q.top().first;
        x = Q.top().second;
        Q.pop();
        for(pair<int,int> it:G[x]){
            y=it.first;
            w=it.second;
            if(dist + w < d[y] && !vis[y]){
                d[y]=dist + w;
                Q.push({-d[y],y});
            }
        }
        vis[x]=true;
    }
    for(int i=2;i<=n;i++) fout<<(d[i]==1e9? 0:d[i])<<' ';

}