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

using namespace std;

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

typedef pair < int, int> pii;

const int INF = 2000000000;
const int NMAX = 50002;

int N, M;
vector < int > Ad[NMAX];
vector < int > Cost[NMAX];

bool in_h[NMAX];
int d[NMAX];

void Read()
{
    fin >> N >> M;

    for( int i = 1; i <= M; ++i )
    {
        int a, b, d;

        fin >> a >> b >> d;

        Ad[a].push_back( b );
        Cost[a].push_back( d );
    }
}

void Do()
{
    priority_queue< pii, vector < pii >, greater < pii > > H;

    for( int i = 1; i <= N; ++i )
        d[i] = INF;

    d[1] = 0;

    H.push( make_pair( 0, 1 ) );
    int nod;

    while( !H.empty() )
    {
        nod = H.top().second;
        H.pop();

        if( in_h[nod] )continue;
        else in_h[nod] = true;

        for( int i = 0; i < Ad[nod].size(); ++i )
        {
            int w = Ad[nod][i];

            if( d[nod] + Cost[nod][i] < d[w] )
            {
                d[w] = d[nod] + Cost[nod][i];
                H.push( make_pair( d[w], w ) );
            }
        }
    }

    for( int i = 2; i <= N; ++i )
        if( d[i] == INF ) fout << 0 << ' ';
    else
        fout << d[i] << ' ';

}
int main()
{
    Read();
    Do();
    return 0;
}