#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;
#define int unsigned int
#define MAXN 50001
class cmp{
    public:
    bool operator()(const pair<int,int> & a,const pair<int,int> & b)const {
        return a.first>b.first;
        }
};
int dist[MAXN];
vector<pair<int,int>> adj[MAXN];
signed main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int v1,v2,dist;
        f>>v1>>v2>>dist;
        adj[v1].push_back({v2,dist});
    }
    memset(dist,-1,sizeof(dist));
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
    pq.push({0,1});
    dist[0]=0;
    while(pq.size()){
        auto [d1,nod]=pq.top();
        pq.pop();
        for(auto [vecin,d2]:adj[nod]){
            if(dist[vecin]>d2+d1){
                dist[vecin]=d2+d1;
                pq.push({d2+d1,vecin});
            }
        }
    }
    for(int i=2;i<=n;i++)
        g<<(dist[i]==-1?0:dist[i])<<" ";
    return 0;
}