#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

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

const int Inf = 1 << 30;
const int Max = 5e4 + 1;

class Dijkstra {
public:
    void dijkstra(int node, vector<pair<int,int>> graph[], vector<int>& d) {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        bitset<Max> v;
        q.push({0, node});
        d[node] = 0;
        while(!q.empty()) {
            node = q.top().second;
            q.pop();
            if(v[node] == 1)
                continue;
            v[node] = 1;
            for(auto i: graph[node]) {
                int cost = i.second;
                int neighbour = i.first;
                if(d[node] + cost < d[neighbour]) {
                    d[neighbour] = d[node] + cost;
                    q.push({d[neighbour], neighbour});
                }
            }
        }
    }

    void print(int n, vector<int> d) {
        for(int i = 2; i <= n; ++i) {
            if(d[i] == Inf) {
                fout << "0 ";
            }
            else {
                fout << d[i] << " ";
            } 
        }
    }
};

int main() {
    vector<pair<int,int>> graph[Max];
    vector<int> d(Max, Inf);
    Dijkstra D;
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        graph[x].push_back({y, z});
    }
    D.dijkstra(1, graph, d);
    D.print(n, d);
    fin.close();
    fout.close();
    return 0;
}