#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

int main() {
    FILE *fin, *fout;
    int dist[50001];
    vector <pair<int,int> > v[50001];
    set <pair<int,int> > s;
    int i, j, x, y, z, front, back, n, m, d, nodcurent, nod, distanta;

fin = fopen("dijkstra.in", "r");
fout = fopen("dijkstra.out", "w");

fscanf(fin,"%d%d", &n, &m);
for(i=1;i<=m;i++){
    fscanf(fin,"%d%d%d", &x, &y, &z);
v[x].push_back(make_pair(y, z));
}
for(i=2;i<=n;i++){
    dist[i]=1000000001;
}
dist[1]=0;

s.insert(make_pair(0, 1));
while(s.empty()==false){
    nod=(*s.begin()).second;
    d=(*s.begin()).first;
    s.erase(s.begin());
    if(v[nod].empty()==false){
    for(i=0;i<=v[nod].size()-1;i++){
            nodcurent=v[nod][i].first;
            distanta=v[nod][i].second;
        if(dist[nodcurent]>d+distanta){

            if(dist[nodcurent]!=1000000001)
                s.erase(s.find(make_pair(dist[nodcurent], nodcurent)));
            dist[nodcurent]=distanta+dist[nod];
            s.insert(make_pair(dist[nodcurent], nodcurent));
        }
    }
    }
}



for(i=2;i<=n;i++){
    fprintf(fout,"%d ", dist[i]);
}
fclose(fin);
fclose(fout);
        return 0;
}