#include <fstream>
#include <vector>
#include <set>
#include <cstring>

#define oo 10000000
#define Max_Size 50009

using namespace std;

const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";

int N, M;

vector < pair < int , int > > V[Max_Size];
vector < int > Distance;

set < pair < int , int > > my_Q;

inline void Dijkstra()
{
    my_Q.insert( make_pair(1, 0) );

    while(!my_Q.empty())    {
        pair < int , int > nod = *my_Q.begin();
        my_Q.erase(*my_Q.begin());

        for(vector < pair< int, int> > :: iterator val = V[nod.first].begin(); val != V[nod.first].end(); ++val)
            if(Distance[(*val).first] > nod.second + (*val).second)    {
                my_Q.erase( make_pair((*val).first, Distance[(*val).first]) );

                Distance[(*val).first] = nod.second + (*val).second;

                my_Q.insert( make_pair((*val).first, Distance[(*val).first]) );
            }
    }
}

int main()
{
    ifstream f(iname); ofstream g(oname);

    f >> N >> M;
    Distance.resize(N + 1, oo);

    for(int i = 1, x, y, cost; i <= M; ++i) {
        f >> x >> y >> cost;
        V[x].push_back(make_pair(y, cost));
    }

    Distance[1] = 0;
    Dijkstra();

    for(int i = 2; i <= N; ++i) g << ( Distance[i] != oo ? Distance[i] : 0) << ' ';
    g << '\n';

    g.close();
    return 0;
}