#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
vector<vector<pair<int,ll>>>adj(50000);
long long d[50000];
bool vis[50000];
struct cmp{
    bool operator()(int a, int b){
        return d[a] > d[b];
    }
};
int main()
{   
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    cin >> n >> m;
    for(int i = 0;i<m;i++){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        a--;
        b--;
        adj[a].push_back({b,c});

    }
    priority_queue<int,vector<int>,cmp>pq;
    for(int i = 0;i<n;i++){
        d[i] = 1e15;
    }
    d[0] = 0;
    vis[0] = 1;
    pq.push(0);
    while(pq.size()){
        int nod = pq.top();
        pq.pop();
        vis[nod] = 0;
        for(auto v : adj[nod]){
            int vecin = v.first;
            int dist = v.second;
            if(d[nod] + dist < d[vecin]){
                d[vecin] = d[nod] + dist;
                if(!vis[vecin]){
                    vis[vecin] = 1;
                    pq.push(vecin);
                }
            }
        }
    }
    for(int i =1;i<n;i++) cout << d[i]<<" ";
    

    return 0;
}