#include <fstream>
#include <vector>
 
#define DIM 50010
#define INF 0x3f3f3f3f
 
using namespace std;
 
vector<pair<int, int>> G[DIM];
int D[DIM], V[DIM], P[DIM], H[DIM];
 
int n, m, dH, x, y, k, aux, i, c, inHeap;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
void Up(int poz);
void pop();
 
int main() 
{
    fin >> n >> m;
    for (i=1;i<=m;i++) 
    {
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }
 
    for (i=1;i<=n;i++)
        D[i] = INF;
    D[1] = 0;
 
    H[1] = 1;
    P[1] = 1;
    dH = 1;
    while (dH) 
    {
        k = H[1];
        pop();
 
        V[k] = 1;
 
        for (i=0;i<G[k].size(); i++) {
            x = G[k][i].first;
            if (D[x] > D[k] + G[k][i].second) {
                inHeap = (D[x] != INF);
                D[x] = D[k] + G[k][i].second;
                if (inHeap)
                    Up( P[x] );
                else {
                    dH ++;
                    H[dH] = x;
                    P[x] = dH;
                    Up(dH);
                }
            }
        }
 
    }
 
    for (i=2;i<=n;i++)
        if (D[i] == INF)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";
 
    return 0;
}

void pop() 
{
    H[1] = H[dH--];
    P[H[1]] = 1;
 
    int p = 1, c = 2;
    while (c <= dH) {
        if (c + 1 <= dH && D[ H[c+1] ] < D[ H[c] ])
            c++;
 
        if (D[ H[p] ] > D[ H[c] ]) {
            aux = H[p];
            H[p] = H[c];
            H[c] = aux;
            P[ H[p] ] = p;
            P[ H[c] ] = c;
            p = c;
            c = 2*p;
        } else
            break;
    }
}
 
void Up(int poz) 
{
    int c = poz, p = c/2;
    while (p != 0 && D[ H[c] ] < D[ H[p] ]) {
        aux = H[c];
        H[c] = H[p];
        H[p] = aux;
        P[H[p]] = p;
        P[H[c]] = c;
        c = p;
        p = c/2;
    }
}