#include <fstream>
#include <queue>
#include <vector>
#define inf 2000000000
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod{
    nod(int a,int b):pret(a),nr(b){}
    int pret,nr;
};
struct cmp{bool operator()(const nod &m1,const nod &m2){return m1.pret>m2.pret;}};

int main()
{
    int n,m;
    vector<int> v[50001],pr[50001];

    f>>n>>m;

    for(int i=1;i<=m;i++){
        int x,y,cs;
        f>>x>>y>>cs;
        v[x].push_back(y);
        pr[x].push_back(cs);
    }

    int d[50001]={};
    for(int i=2;i<=n;i++)
        d[i]=inf;

    priority_queue<nod,vector<nod>,cmp> pq;
    bool ok[50001]={};

    pq.push(nod(0,1));

    while(!pq.empty()){
        nod ax=pq.top();
        pq.pop();
        if(ok[ax.nr])
            continue;
        ok[ax.nr]=1;
        for(unsigned j=0;j<v[ax.nr].size();j++){
            int arnr=v[ax.nr][j],axpr=pr[ax.nr][j];
            if(d[ax.nr]+pr[ax.nr][j]<d[v[ax.nr][j]]&&!ok[v[ax.nr][j]]){
                d[v[ax.nr][j]]=d[ax.nr]+pr[ax.nr][j];
                pq.push(nod(d[v[ax.nr][j]],v[ax.nr][j]));
            }
        }
    }

    for(int i=2;i<=n;i++)
        g<<(d[i]==inf ? 0 : d[i])<<" ";

    return 0;
}