#include<fstream>
#include<queue>
#define NMAX 500001
#define INF 1e9

//in-out
std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");

//data
class Node{
public:
    int cost, y;
    Node(int cost, int y): cost(cost), y(y) {}

    bool operator < (const Node& other) const {
        return this->cost > other.cost;
    }
};

std::vector<Node> G[NMAX];
std::vector<int> dist(NMAX);
std::priority_queue<Node> pq;
int n, m;

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

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

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

int main(){
    readData();
    solve();
    printSol();
    return 0;
}