#include <fstream>
#include <map>
#include <vector>
#define NMAX 50005
#define MAX 2100000000

using namespace std;

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

struct A
{
    int dest, cost;
};

multimap < int, int > M;
vector < A > v[NMAX];
int r[NMAX];

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

    fin >> n >> m;
    while ( m-- )
    {
        fin >> x >> y >> z;
        v[x].push_back ( { y, z } );
    }

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

    for ( i = 0 ; i < v[1].size() ; i++ ) M.insert ( { v[1][i].cost, v[1][i].dest } );
    while ( M.empty() == 0 )
    {
        x = M.begin() -> first;
        y = M.begin() -> second;
        M.erase ( M.begin() );

        if ( x < r[y] )
        {
            r[y] = x;
            for ( i = 0 ; i < v[y].size() ; i++ ) M.insert ( { x + v[y][i].cost, v[y][i].dest } );
        }
    }

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

    return 0;
}