#include <fstream>
#define INF ( 1 << 30 )
#define MAX 250005
struct muchie
{
    int x, y, cost;
} v[MAX];

using namespace std;

int n, m;
int d[50005];

void read ()
{
    ifstream f("dijkstra.in");

    f >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        f >> v[i].x >> v[i].y >> v[i].cost;
        if ( v[i].x == 1 )
            d[ v[i].y ] = v[i].cost;
    }

    f.close();
}

void init ()
{
    d[1] = 0;
    for (int i = 2; i <= n; i ++ )
        if ( !d[i] )
            d[i] = INF;
}

void solve ()
{
    init();
    int ok = 0;
    while ( !ok )
    {
        ok = 1;
        for (int i = 1; i <= m; i ++ )
        {
            if ( d[ v[i].y ] > d[ v[i].x ] + v[i].cost )
            {
                ok = 0;
                d[ v[i].y ] = d[ v[i].x ] + v[i].cost;
            }

        }
    }
}

void write ()
{
    ofstream g ("dijkstra.out");

    for (int i = 2; i <= n; i ++ )
    {
        if ( d[i] != INF )
            g << d[i] << " ";
        else
            g << "0 ";
    }

    g.close();
}

int main()
{
    read();
    solve();
    write();
    return 0;
}