#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

const int NMAX = 50007;
const int INF = 1000000007;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int Dp[NMAX];
int Viz[NMAX];
priority_queue < pair < int, int > > q;
vector < pair < int, int > > v[NMAX];
int n, m;

void dijkstra(int node) {
    q.push(make_pair(0, node));
    while(! q.empty()) {
        node = q.top().y;
        int cost = q.top().x;
        if(Viz[node] == 0) {
            Viz[node] = 1;
            q.pop();
            for(vector < pair < int, int > > :: iterator it = v[node].begin(); it != v[node].end(); ++it) {
                if(Dp[it->x] > Dp[node] + it->y) {
                    Dp[it->x] = Dp[node] + it->y;
                    q.push(make_pair(-Dp[it->x], it->x));
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    for(int i = 2; i <= n; ++i) {
        Dp[i] = INF;
    }
    dijkstra(1);
    for(int i = 2; i <= n; ++i) {
        if(Dp[i] == INF) {
            Dp[i] = 0;
        }
        cout << Dp[i] << " ";
    }
    return 0;
}