#include <fstream>
#include <vector>
#define N 50010
#define oo 500100000
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void sw(int, int), heap_up(int), heap_down(int);
int n, m, x, y, z, i, H[N], P[N], D[N], ord(int, int);
vector<pair<int, int> > v[N];

int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    for(i = 1; i <= n; i++)
    {
        H[i] = P[i] = i;
        D[i] = oo;
    }
    D[1] = 0;
    m = n;
    while(m && D[H[1]] < oo)
    {
        x = H[1];
        sw(1, m);
        m--;
        heap_down(1);
        for(auto it:v[x])
            if(D[it.first] > D[x] + it.second)
            {
                D[it.first] = D[x] + it.second;
                heap_up(P[it.first]);
            }
    }
    for(i = 2; i <= n; i++)
        if(D[i] < oo)
            g<<D[i]<<' ';
        else
            g<<"0 ";
    return 0;
}
void heap_down(int T)
{
    for(;;)
    {
        int F = 2*T;
        if(F > m) return;
        if(F < m)
            if(ord(F+1, F))
                F++;
        if(ord(F, T))
        {
            sw(F, T);
            heap_down(F);
        }
        else return;
    }
}
void heap_up(int F)
{
    for(;;)
    {
        int T = F/2;
        if(!F) return;
        if(ord(F, T))
        {
            sw(F, T);
            heap_up(T);
        }
        else return;
    }
}
void sw(int I, int J)
{
    swap(H[I], H[J]);
    P[H[I]] = I;
    P[H[J]] = J;
}
int ord(int I, int J)
{
    return D[H[I]] < D[H[J]];
}