#include <iostream>
#include <fstream>
#include <vector>
 
#define INF 1<<30
#define NEW 0
#define FOUND 1
#define FINISHED 2
 
using namespace std;
 
typedef struct {
    int id;
    int c;
} Edge;
 
typedef struct {
    int n;
    vector < vector <Edge> > V;
} Graph;
 
typedef struct {
    int n;
    Edge *v;
    int *index;
} Heap;
 
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
Heap H = {0, NULL, NULL};
Graph G;
int *d;
char *visited;
 
void swap (int i1, int i2) {
    H.index[H.v[i1].id] = i2;
    H.index[H.v[i2].id] = i1;
     
    Edge c = H.v[i1];
    H.v[i1] = H.v[i2];
    H.v[i2] = c;
}
 
void addHeap (Edge e) {
    int i = H.n;
    H.v[i] = e;
    H.index[e.id] = i;
     
    while (i >= 0 && H.v[i].c < H.v[(i-1)/2].c) {
        int aux = (i-1)/2;
        swap(i, aux);
        i = aux;
    }
     
    ++(H.n);
}
 
void popHeap () {
    --(H.n);
    H.v[0] = H.v[H.n];  
     
    int i = 0, ok = 0;
    while(!ok) {
        int l = 2*i+1, r = 2*i+2;
        if (r < H.n && (H.v[i].c > H.v[l].c || H.v[i].c > H.v[r].c)) {
            if (H.v[l].c < H.v[r].c) {
                swap(i, l);
                i = l;
            } else {
                swap(i, r);
                i = r;
            }
        } else if (l < H.n && H.v[i].c > H.v[l].c) {
            swap(i, l);
            i = l;
        } else {
            ok = 1;
        }
    }
     
}
 
void modCost (int id, int nc) {
    int i = H.index[id];
    H.v[i].c = nc;
     
    while (i >= 0 && H.v[i].c < H.v[(i-1)/2].c) {
        int aux = (i-1)/2;
        swap(i, aux);
        i = aux;
    }
     
}
     
void read() {
    in >> G.n;
     
    H.v = new Edge[G.n];
    H.index = new int[G.n + 1];
     
    for (int i = 0; i <= G.n; ++i) {
        vector <Edge> a;
        G.V.push_back(a);
    }
     
    int m;
    in >> m;
     
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        in >> x >> y >> z;
        Edge aux = {y, z};
        G.V[x].push_back(aux);
    }
}
 
void dijkstra () {
    d = new int[G.n + 1];
    for (int i = 0; i <= G.n; ++i) {
        d[i] = INF;
    }
     
    visited = new char[G.n+1]();
    visited[1] = FINISHED;
     
    for (unsigned int i = 0; i < G.V[1].size(); ++i) {
        addHeap(G.V[1][i]);
        d[G.V[1][i].id] = G.V[1][i].c;
        visited[G.V[1][i].id] = FOUND;
    }
     
    while (H.n) {
         
        int id = H.v[0].id;
        popHeap();
         
        for (unsigned int i = 0; i < G.V[id].size(); ++i) {
            int test = d[id] + G.V[id][i].c;
            if (d[G.V[id][i].id] > test) {
                d[G.V[id][i].id] = test;
                if(visited[G.V[id][i].id]) {
                    modCost(G.V[id][i].id, test);
                } else {
                    Edge temp = {G.V[id][i].id, test};
                    addHeap(temp);
                    ++visited[G.V[id][i].id];
                }
            }
        }
         
        ++visited[id];
    }
}
     
int main(void) {
    read();
     
    dijkstra();
     
    for (int i = 2; i <= G.n; ++i) {
        if (d[i] == INF) {
            out << 0 << " ";
        } else {
            out << d[i] << " ";
        }   
    }
     
    return 0;
}