#include<bits/stdc++.h>
#define int long long

using namespace std;

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

int n , m;
struct Iris{
    int nod , dist;
};

signed main(){
    fin >> n >> m;
    vector<vector<Iris>> graf(n + 1);
    for(int i = 1 ; i <= m ; i++){
        int x , y , d;
        fin >> x >> y >> d;
        graf[x].push_back({y , d});
    }
    vector<int> dist(n + 1 , 2e9);
    dist[1] = 0;
    priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> pq;
    pq.push({0 , 1});
    while(!pq.empty()){
        int d = pq.top().first;
        int nod = pq.top().second;
        pq.pop();
        if(d > dist[nod]) continue;
        for(auto vecin : graf[nod]){
            int vnod = vecin.nod;
            int d = vecin.dist;
            if(dist[vnod] > dist[nod] + d){
                dist[vnod] = dist[nod] + d;
                pq.push({dist[vnod] , vnod});
            }
        }
    }
    for(int i = 2 ; i <= n ; i++){
        if(dist[i] == 2e9) fout << 0 <<" ";
        else fout << dist[i] <<" ";
    }
}