#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define mult 10000000

vector< pair<int, int> > v[50001];
set<pair<int,int> > s;
int dist[50002], viz[50002];
int n, m;

void dijkstra()
{
    int nod, distanta;
    for( int i = 1; i <= n ; i ++ )
        dist[i] = mult;

    s.insert( make_pair( 0, 1 ) );
    int nr = n;
    while( nr )
    {
        nod = s.begin()->second;
        distanta = s.begin()->first;

        if( viz[nod] == 0 )
        {
                viz[nod] = 1;
                nr--;

            s.erase(s.begin());

            for( vector<pair<int, int > >::iterator it = v[nod].begin(); it != v[nod].end(); ++it )
                if( dist[ it->first ] > distanta + it->second )
                {
                    dist[ it->first ] = distanta + it->second;
                    s.insert( make_pair( distanta + it->second, it->first ));
                }
        }
    }

    for( int i = 2; i <= n ; i ++ )
        if( dist[i] == mult )
            g << 0 << " ";
        else
            g << dist[i] << " ";

}

int main()
{
    f >> n >> m;

    int x, y, z;
    for( int i = 0; i < m; i ++ )
    {
        f >> x >> y >> z;
        v[x].push_back( make_pair( y, z ) );
    }

    dijkstra();

    return 0;
}