#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <iterator>
#define NMAX 50005
#define INF 300000
using namespace std;

class vfval{
public:
    int vf,val;
    vfval(int vf,int val): vf{vf},val{val}{}
};

class comparator{
public:
    int vf,val;
    bool operator()(vfval a,vfval b){
        return a.val > b.val;
    }
};

int main()
{
    int l1,l2,val,n,m;
    vector<vfval> v[NMAX];
    int d[NMAX];
    int vizitat[NMAX]={0};
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f >> n >> m;
    vizitat[1]=1;
    for(int i=0;i<m;i++){
        f >> l1 >> l2 >> val;
        v[l1].push_back(vfval(l2,val));
    }
    for(int i=2;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    priority_queue<vfval,vector<vfval>,comparator> que;
    que.push(vfval(1,0));
    while(!que.empty()){
        int cost= que.top().val;
        int vf = que.top().vf;
        que.pop();
        for(vector<vfval>::iterator it=v[vf].begin();it!=v[vf].end();it++){
            if(!vizitat[it->vf] && d[it->vf] > cost + it->val){
                d[it->vf] = cost + it->val;
                que.push(vfval{it->vf,d[it->vf]});
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(d[i]!=INF)
            g << d[i] << ' ';
        else g << 0 << ' ';
    g.close();
    f.close();
    return 0;
}