#include <fstream>
#include <vector>
#include <queue>

#define INF 1e9

using namespace std;

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

void dijkstra ( int nod );

int n, m;

int x, y, z;

int d[50137];

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

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

int main()
{
    in >> n >> m;
    for ( register int i = 1 ; i <= m ; ++i )
    {
        in >> x >> y >> z;
        v[x].push_back ( { y, z } );
    }
    dijkstra (1);
    for ( register int i = 2 ; i <= n ; ++i )
        if ( d[i] != INF )
            out << d[i] << " ";
        else
            out << 0 << " ";
    return 0;
}

void dijkstra ( int nod )
{
    for ( register int i = 1 ; i <= n ; ++i )
        d[i] = INF;
    q.push ( { nod, 0 } );
    while ( !q.empty () )
    {
        x = q.top ().first;
        z = q.top ().second;
        q.pop ();
        if ( d[x] == INF )
        {
            d[x] = z;
            for ( auto i : v[x] )
                if ( d[i.first] == INF )
                    q.push ( { i.first, i.second + z } );
        }
    }
}