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

using namespace std;

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

struct A
{
    int y, val;
};

vector < A > v[50001];
queue < int > q;
map < int, int > a;

map < int , int > :: iterator it;

int r[50001];

void dij();

int main()
{
    int n, m, i, x, y, z;

    fin >> n >> m;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> z;
        v[x].push_back ( { y, z } );
    }

    for ( i = 1 ; i <= n ; i++ ) r[i] = 1000000;
    r[1] = 0;

    q.push ( 1 );
    dij();

    for ( i = 2 ; i <= n ; i++ ) fout << r[i] << ' ';

    return 0;
}

void dij()
{
    int i, nod;

    while ( q.empty() == 0 )
    {
        nod = q.front();
        q.pop();

        for ( i = 0 ; i < v[nod].size() ; i++ ) a.insert ( { r[nod] + v[nod][i].val, v[nod][i].y } );

        for ( it = a.begin() ; it != a.end() ; it++ )
            if ( it -> first < r[it -> second] )
            {
                r[it -> second] = it -> first;
                q.push ( it -> second );
                break;
            }
    }
}