// Solutie de 90 de puncte
/*
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

struct A
{
    unsigned short b, c;
};

queue < unsigned short > q;
vector < A > a[50001];

void bfs ( int nod );

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

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

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

    bfs ( 1 );

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

    return 0;
}

void bfs ( 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 );
            }
    }
}
*/

#include <iostream>
#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];
multimap < int, int > a;

map < int, int > :: iterator it;

int r[50001];
bool viz[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 = 2 ; i <= n ; i++ ) r[i] = 2000000000;
    r[1] = 0;

    a.insert ( { 0, 1 } );
    dij();

    for ( i = 2 ; i <= n ; i++ )
    {
        if ( r[i] == 2000000000 ) fout << 0 << ' ';
        else fout << r[i] << ' ';
    }

    return 0;
}

void dij()
{
    int i, nod;

    while ( a.empty() == 0 )
    {
        nod = a.begin() -> second;
        a.erase ( a.begin() );

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

            viz[nod] = 1;
        }
    }
}