#include <fstream>
#include <set>
#include <vector>

using namespace std;

set< pair<int,int> > v;

vector<pair<int,int> > l[50005];
vector<pair<int,int> >::iterator it;

int n,m,i,x,y,c,d[50005],Min,k;

const int INF = 2000000000;

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=m;i++) {
        f>>x>>y>>c;
        l[x].push_back(make_pair(y,c));
    }
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    v.insert(make_pair(0,1));
    while(!v.empty()) {
        Min=v.begin()->first;
        k=v.begin()->second;
        v.erase(*v.begin());
        for(it=l[k].begin();it!=l[k].end();it++)
            if(d[it->first]>d[k]+it->second) {
                d[it->first]=d[k]+it->second;
                v.insert(make_pair(d[it->first],it->first));
            }
    }
    for(i=2;i<=n;i++)
        if(d[i]!=INF)
            g<<d[i]<<" ";
        else
            g<<"0\n";
    return 0;
}