#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 50003;
const int M = 250003;
const int inf = M*1000;

int n, m, nr, cost[M], vf[M], lst[N], urm[M], d[N], q[M*1000];
bool viz[N];

void adauga( int x, int y, int c )
{
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    cost[nr] = c;
    lst[x] = nr;
}

int main()
{
    int i, x, y, c, poz;
    in >> n >> m;
    for ( i = 1; i <= m; i++ )
    {
        in >>x >> y >>c;
        adauga(x,y,c);
    }

    for ( i = 1; i <= n; i++ )
        d[i] = inf;

    int p, u;
    p = u = 1;
    q[p] = 1;
    d[1] = 0;
    viz[1] = true;

    while( p <= u )
    {
        x = q[p];
        viz[x] = false;
        poz = lst[x];
        while( poz != 0 )
        {
            y = vf[poz];
            c = cost[poz];
            if ( d[y] > d[x] + c )
            {
                if ( viz[y] == false )
                {
                    u++;
                    q[u] = y;
                    viz[y] = true;
                }
                d[y] = d[x] + c;
            }
            poz = poz[urm];
        }
        p++;
    }
    for ( i = 2; i <= n; i++ )
        out << d[i]<<' ';
    return 0;
}