#include <iostream>
#include <fstream>
#include <set>
#include <vector>
using namespace std;
#define MAXn 50100
#define InF 1000000000

int n, m, d[MAXn];
vector <int> G[MAXn], C[MAXn];
set< pair<int, int> > T;

void Dijkstra()
{
    for(int i = 2; i <= n; i++) d[i] = InF;

    T.insert( make_pair(0, 1) );

    while(!T.empty())
    {
        int cost,x;
        cost = (*T.begin()).first;
        x = (*T.begin()).second;
        T.erase(*T.begin());
        for(int i = 0; i < G[x].size(); i++)
            if(d[ G[x][i] ] > cost + C[x][i] )
                d[ G[x][i] ] = cost + C[x][i], T.insert(make_pair(d[G[x][i]],G[x][i]));
    }
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int i, a, b, c;

    f>>n>>m;

    for(i = 1; i <= m; i++)
    {
        f>>a>>b>>c;
        G[a].push_back(b);
        C[a].push_back(c);
    }

    f.close();
    Dijkstra();

    for(i = 2; i <= n; i++)
        (d[i]==InF) ? g<<"0 " :  g<<d[i]<<" ";

    g.close();

    return 0;
}