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

using namespace std;

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

const int INF = ( 1 << 30 );
const int NMAX = 50005;

int N, M;

typedef pair < int, int > Pair;

int d[NMAX];

vector <int> Ad[NMAX];
vector <int> Cost[NMAX];

bool vis[NMAX];

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

    int a, b, d;

    while( fin >> a >> b >> d )
    {
        ++M;

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

    fin.close();
}

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

    d[1] = 0;

    priority_queue < Pair, vector<Pair>, greater<Pair> > H;

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

    int nod, w;

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

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

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

            if( d[w] > d[nod] + Cost[nod][i] )
            {
                d[w] = d[nod] + Cost[nod][i];

                H.push( make_pair( d[w], w ) );
            }
        }
    }
}

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

    fout.close();
}

int main()
{
    Read();
    Do();
    Print();

    return 0;
}