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

using namespace std;

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

struct A
{
    int b, c;
};

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

void dfs ( int nod );

int n, m, i, x, y, c, p, r[50001], lg[50001];

int main()
{
    fin >> n >> m;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> c;
        a[x].push_back( { y, c } );
        //a[y].push_back( { x, c } );
    }

    for ( i = 1 ; i <= n ; i++ ) lg[i] = a[i].size();

    dfs ( 1 );

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

    return 0;
}

void dfs ( int nod )
{
    q.push ( nod );
    while ( q.empty() == 0 )
    {
        x = q.front();
        q.pop();

        for ( i = 0 ; i < lg[x] ; i++ )
            if ( r[x] + a[x][i].c < r[a[x][i].b] || r[a[x][i].b] == 0 )
            {
                r[a[x][i].b] = r[x] + a[x][i].c;
                q.push ( a[x][i].b );
            }
    }
}