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

using namespace std;

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

#define MAXN 50100
#define INF 1000000000

int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;

void solve()
{
    int i, j, k, val, x;
    for(i = 2; i <= N; i++) d[i] = INF;
    T.insert(make_pair(0, 1));
    while( T.size() > 0 )
    {
        val = (*T.begin()).first, x = (*T.begin()).second;
        T.erase(*T.begin());
        for(i = 0; i < G[x].size(); i++)
            if(d[ G[x][i] ] > val + C[x][i])
            {
                d[ G[x][i] ] = val + C[x][i];
                T.insert(make_pair(d[G[x][i]],G[x][i]));
            }
    }
}

int main()
{
    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);
    }
    solve();
    for(i = 2; i <= N; i++)
        if(d[i] != INF)
            g << d[i] << " ";
    return 0;
}