#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
#define maxn 50010
#define inf 99999999
#define pii pair<int, int>
#define mkp make_pair

int N, M;
int D[maxn], viz[maxn];
vector<pii> G[maxn];
set<pii>::iterator it, fnd;
set<pii> heap;

int main() {
    FILE *f1=fopen("dijkstra.in", "r"), *f2=fopen("dijkstra.out", "w");
    int i, j, p, q;

    fscanf(f1, "%d %d\n", &N, &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d %d\n", &p, &q, &j);
         G[p].push_back( mkp(q, j) );
    }

    heap.insert( mkp(0, 1) );
    for(i=2; i<=N; i++) {
         D[i] = inf;
         heap.insert( mkp(inf, i) );
    }

    while(heap.size()) {
         it = heap.begin();
         int nod = (*it).second;
         int cost = (*it).first;

         for(i=0; i<G[nod].size(); i++) {
              if(D[ G[nod][i].first ] > cost + G[nod][i].second) {
                   fnd = heap.find( mkp(D[ G[nod][i].first ], G[nod][i].first) );
                   D[ G[nod][i].first ] = cost + G[nod][i].second;

                   if(fnd != heap.end()) {
                        heap.erase(fnd);
                        heap.insert( mkp(D[ G[nod][i].first ], G[nod][i].first) );
                   }
              }
         }

         heap.erase(it);
    }

    for(i=2; i<=N; i++) {
         fprintf(f2, "%d ", D[i]);
    } fprintf(f2, "\n");

    fclose(f1); fclose(f2);
    return 0;
}