#include <bits/stdc++.h>
#define nmax 50005
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,dp[nmax];
bool solved[nmax];
priority_queue<pair<int,int> > pq;
vector<pair<int,int> > lista[nmax];
void read(){
    in >> n >> m;
    for(int i=1; i<=m; i++){
        int a,b,c;
        in >> a >> b >> c;
        lista[a].push_back({b,c});
    }
}
void dijkstra(int node){
    for(int i=1; i<=n; i++){
        dp[i] = INT_MAX;
    }
    dp[node] = 0;
    pq.push({0,node});
    while(!pq.empty()){
        int nod = pq.top().second;
        pq.pop();
        if(solved[nod]) continue;
        solved[nod]=true;
        for(auto x:lista[nod]){
            if(dp[x.first] > dp[nod]+x.second){
                dp[x.first] = dp[nod]+x.second;
                pq.push({-dp[x.first],x.first});
            }
        }
    }
    for(int i=1; i<=n; i++){
        if(i!=node) out << dp[i] << ' ';
    }
}
int main()
{
    read();
    dijkstra(1);
    return 0;
}