#include <fstream>
#include <map>
#include <vector>
#include <bitset>
#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];
bitset < NMAX > viz;
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 ( { 0, 1 } );
    while ( M.empty() == 0 )
    {
        y = M.begin() -> second;
        M.erase ( M.begin() );

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

            viz[y] = 1;
        }
    }

    for ( i = 2 ; i <= n ; i++ )
        if ( r[i] != MAX ) fout << r[i] << ' ';
        else fout << 0 << ' ';

    return 0;
}