#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int maxn = 50000;
vector<int> adj[maxn + 1];

struct edge {
    int to;
    int w;

    edge(int to, int w) {
        this->to = to;
        this->w = w;
    }
    bool operator<(const edge &a) const {
        if (w != a.w)
            return w < a.w;
        return to < a.to;
    }
    bool operator>(const edge &a) const {
        if (w != a.w)
            return w > a.w;
        return to < a.to;
    }
};
map<int, int> routes[maxn + 1];
int distmin[maxn + 1];
bool visited[maxn + 1];

void dijkstra(int start) {
    priority_queue<edge, vector<edge>, greater<edge>> goolah;
    goolah.push(edge(start, 0));
    while (!goolah.empty()) {
        edge curr = goolah.top();
        goolah.pop();
        if (visited[curr.to])
            continue;
        //cout << curr.to << ' ' << curr.w << '\n';
        distmin[curr.to] = curr.w;
        visited[curr.to] = true;
        for (int child: adj[curr.to]) 
            if (!visited[child]){
                edge update(child, curr.w + routes[curr.to][child]);
                goolah.push(update);
            }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].push_back(v);
        routes[u][v] = w;
    }

    dijkstra(1);
    for (int i = 2; i <= n; i++)
        fout << distmin[i] << ' ';

    return 0;
}