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

using namespace std;

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

const int NMAX = 100001;
const int INF = 2000000000;

typedef pair < int, int >  pii;

int N, M, P;

bool vis[NMAX];
int dist[NMAX];

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

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

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

    int x, y, c;
    for( int i = 1; i <= M; ++i )
    {
        fin >> x >> y >> c;

        Ad[x].push_back( make_pair( y, c ) );
    }

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

void Dijkstra( int x )
{
    dist[x] = 0;

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

    while( H.size() )
    {
        int nod = H.top().second;
        int d = H.top().first;

        H.pop();

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

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

            if( dist[w.first] > d + w.second )
            {
                dist[w.first] = d + w.second;
                H.push( make_pair( dist[w.first], w.first ) );
            }
        }

    }

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