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

std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");

constexpr int N = 5e4+1;
constexpr long long INF = 5e9+1;
struct vertice{
    int node, cost;
};
int n, m;
std::vector<vertice> g[N];
std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> heap;
long long dist[N];
bool selected[N];

void dijkstra(int x0){
    for(int i=1; i<=n; ++i)
        dist[i] = INF;
    dist[x0] = 0;
    heap.push({0, x0});
    while (!heap.empty()){
        int currNode = heap.top().second;
        heap.pop();
        if(selected[currNode]) continue;
        selected[currNode] = true;
        for(auto child : g[currNode]){
            int childNode = child.node;
            int cost = child.cost;
            if(dist[currNode] + cost < dist[childNode]){
                dist[childNode] = dist[currNode] + cost;
                heap.push({dist[childNode], childNode});
            }
        }
    }
    
}

int main(){
    in >> n >> m;
    for(int i=0; i<m; ++i){
        int u, v, cost;
        in >> u >> v >> cost;
        g[u].push_back({v,cost});
    }
    dijkstra(1);
    for(int i=2; i<=n; ++i)
        out << dist[i] << ' ';
}