#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

vector < pair < int, int > > v[100005];

int n, m, i, a, b, s, fv[100005], c;

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

pair <int, int> aux;

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

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

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

    }

    pq.push( {0 , 1} );

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

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

        fv[aux.y] = aux.x;

        for ( i = 0 ; i < v[aux.y].size() ; i++ )
        {
            pq.push( { aux.x + v[aux.y][i].y, v[aux.y][i].x } );
        }

    }

    for ( i = 2 ; i <= n; i++ )
    {
        fout<<fv[i]<<" ";
    }

    return 0;
}