#include <stdio.h>
#include <set>
#include <vector>

using namespace std;

#define MAX_N 260000
#define inf (1 << 31) - 1
#define MAX 50010

set <pair <int, int> > nod;
vector <int> A[MAX_N], C[MAX_N];
int n, m, i, j, k, x ,y, c, l;
int sol[MAX];
bool fol[MAX];

void cit() {
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d %d", &n,&m);
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d",&x, &y, &c);
        A[x].push_back(y);
        C[x].push_back(c);
    }
}

void solve() {
     for (i = 2; i <= n; i++) sol[i] = inf;
        
     nod.insert(make_pair(0, 1));
     while (nod.size()) {
           k = (*nod.begin()).first; x = (*nod.begin()).second;
           nod.erase(nod.begin());
           
           l = A[x].size();
           if (!fol[x])
           for (i = 0; i < l; i++) {
               if (sol[A[x][i]] > C[x][i] + k) {
                  sol[A[x][i]] = C[x][i] + k;
                  nod.insert(make_pair(sol[A[x][i]], A[x][i]));
               }
           }
           fol[x] = 1;
     }
}

void write() {
     for (i = 2; i <= n; i++) 
         if (sol[i] != inf) printf("%d ",sol[i]);
         else printf("0 ");
     printf("\n");
}

int main() {

    cit();
    solve();
    write();

    return 0;
}