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

using namespace std;

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

const int NMAX = 2500002;
vector<pair<int,int>> adj[NMAX];
bool viz[NMAX];
int minCost[NMAX];
int n,m;

void dijkstra(int sursa) {
    for (int i=1;i<=n;i++) {
        minCost[i] = 1e9;
    }
    minCost[sursa] = 0;
    set<pair<int,int>> s;
    s.insert({0,sursa});
    while (!s.empty()) {
        pair<int,int> p = *s.begin();
        s.erase(s.begin());
        int node = p.second;
        if (viz[node]) {
            continue;
        }
        viz[node] = true;
        for (auto v : adj[node]) {
            if (minCost[v.first] > minCost[node] + v.second) {
                minCost[v.first] = minCost[node] + v.second;
                s.insert({minCost[v.first],v.first});
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    int x,y,z;
    for (int i=1;i<=m;i++) {
        fin>>x>>y>>z;
        adj[x].push_back({y,z});
    }
    dijkstra(1);
    for (int i=2;i<=n;i++) {
        fout<<minCost[i]<<" ";
    }
    return 0;
}