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

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

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

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

priority_queue < pair < int, int > , vector < pair < int , int > > , greater < pair < int , int > > > pq;

pair < int, int > aux;

void dijkstra()
{
    pq.push( {0, 1} );

    while ( !pq.empty() )
    {
        aux = pq.top();
        pq.pop();

        if ( cst[aux.y] )
        {
            continue;
        }

        cst[aux.y] = aux.x;

        for ( auto i : G[aux.y] )
        {
            pq.push( {aux.x + i.y , i.x} );
        }

    }

}

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<<cst[i]<<" ";
    }

}