#include<fstream>
#include<queue>
#include<vector>
#define NMAX 50005
#define pb push_back
#define INF 1e9
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct Node{
    int y, cost;
    Node(int y, int cost): y{y}, cost{cost} {}
    bool operator<(const Node& ot) const{
        return this->cost > ot.cost;
    }
};

vector<Node>G[NMAX];
int n, m;
int dist[NMAX];

void read_data(int& n, int &m){
    f >> n >> m;

    for(int i = 1; i<=m; i++){
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back({y, c});
    }
}

void dijkstra(int start){

    priority_queue<Node> pq;
    for(int i =1 ; i<=n; i++){
        dist[i] = INF;
    }
    dist[start] = 0;
    pq.push({start, dist[start]});
    while(!pq.empty()){
        auto top = pq.top();
        pq.pop();
        int node = top.y;
        int cost = top.cost;
        if(dist[node] != cost){
            continue;
        }
        for(const auto& adj: G[node]){
            if(dist[node] + adj.cost < dist[adj.y]){
                dist[adj.y] = dist[node] + adj.cost;
                pq.push({adj.y, dist[adj.y]});
            }
        }
    }
}

void print_sol(){
    for(int i = 2; i<=n; i++){
        dist[i] != INF ? g << dist[i] << ' ' : g << 0 << ' ';
    }
}

int main(){
    read_data(n, m);
    dijkstra(1);
    print_sol();
    return 0;
}