#include <fstream>
#include <climits>
#include <vector>
#include <set>
#define dim 50010
using namespace std;
vector<pair<int,int> >a[dim];
set<pair<int,int> >s;
int d[dim];
int i,n,m,c,nod,vecin,cost,x,y;

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        a[x].push_back({y,c});
    }
    for (i=1;i<=n;i++) {
        d[i]=INT_MAX;
    }
    d[1]=0;
    s.insert({0,1});
    while (!s.empty()) {
        nod=s.begin()->second;
        s.erase(s.begin());
        for (i=0;i<a[nod].size();i++) {
            vecin=a[nod][i].first;
            cost=a[nod][i].second;
            if (d[vecin]>d[nod]+cost) {
                s.erase({d[vecin],vecin});
                d[vecin]=d[nod]+cost;
                s.insert({d[vecin],vecin});
            }
        }
    }
    for (i=2;i<=n;i++) {
        if (d[i]==INT_MAX) fout<<0<<" ";
        else fout<<d[i]<<" ";
    }
    return 0;
}