#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m, a, b, c, viz[50005];

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

vector < pair < int, int > > G[50005];

void dijkstra()
{
    queue < pair < int, int > > q;

    pair < int, int > aux;


    q.push( { 0, 1 } );
    viz[1] = -1;

    while ( !q.empty() )
    {
        aux = q.front();
        q.pop();

        for ( auto i : G[aux.y] )
        {
            if ( viz [i.x] == 0 )
            {
                q.push ( { aux.x + i.y  , i.x } );
                viz[ i.x ] = aux.x + i.y;
            }
        }

    }

}

int main ()
{
    f>>n>>m;

    for ( int i = 1 ; i <= m ; i++ )
    {
        f>>a>>b>>c;

        G[a].push_back( {b, c} );
    }

    dijkstra();

    for ( int i = 2 ; i <= n ; i++ )
    {
        g<<viz[i]<<" ";
    }

    return 0;
}