#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

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

#define mult 10000000

vector< pair<int, int> > v[50001];
vector<pair<int,int> > s;
int dist[50002];
int n, m;

void dijkstra()
{
    int nod, distanta;
    for( int i = 1; i <= n ; i ++ )
        dist[i] = mult;

    s.push_back( make_pair( 0, 1 ) );
    while( !s.empty() )
    {
        nod = s.begin()->second;
        distanta = -(s.begin()->first);

        pop_heap( s.begin(), s.end());
        s.pop_back();

        for( vector<pair<int, int > >::iterator it = v[nod].begin(); it != v[nod].end(); ++it )
            if( dist[ it->first ] > distanta + it->second )
            {
                dist[ it->first ] = distanta + it->second;
                s.push_back( make_pair( -(distanta + it->second), it->first ) );
                push_heap( s.begin(), s.end() );
            }

    }

    for( int i = 2; i <= n ; i ++ )
        if( dist[i] == mult )
            g << 0 << " ";
        else
            g << dist[i] << " ";

}

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

    int x, y, z;
    for( int i = 0; i < m; i ++ )
    {
        f >> x >> y >> z;
        v[x].push_back( make_pair( y, z ) );
    }

    dijkstra();

    return 0;
}