#include <bits/stdc++.h>
#define c first
#define v second

using namespace std;

const int NMAX = 50005;
const int INF = 2000000000;

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

int N, M, x, y, c;
int dist[NMAX];
bool viz[NMAX];

vector < pair< int, int> > Ad[NMAX];
priority_queue < pair < int, int > > H;

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

    for( int i = 1; i <= M; ++i )
    {
        fin >> x >> y >> c;
        Ad[x].push_back( make_pair( c, y ) );
    }
}

void Dijkstra( int v )
{
    H.push( make_pair( 0, v ) );

    for( int i = 1; i <= N; ++i )
            dist[i] = INF;
    dist[v] = 0;

    while( H.size() )
    {
        int nod = H.top().v;
        int d = H.top().c;
        H.pop();

        if( viz[nod] ) continue;
        else viz[nod] = 1;

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

            if( dist[w] > dist[nod] + dw )
            {
                dist[w] = dist[nod]+dw;
                H.push( make_pair( dist[w], w ) );
            }
        }
    }
}
void Solve()
{
    Read();
    Dijkstra( 1 );

    for( int i = 2; i <= N; ++i )
        if( dist[i] != INF )fout << dist[i] << ' ';
        else fout << 0 << ' ';
}
int main()
{
    Solve();
    return 0;
}