#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;
struct child {
    int node;
    int w;
    child (int node, int w) {
        this->node = node;
        this->w = w;
    }
};
vector<child> 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;
    }
};
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 (child elem: adj[curr.to]) 
            if (!visited[elem.node]){
                edge update(elem.node, curr.w + elem.w);
                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(child(v, w));
    }

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

    return 0;
}