/*
 * Catun - Supr*
 * O(n^2*logn)
 */
#include<fstream>
#include <vector>
#include <queue>
#define NMAX 36005
#define MMAX 2*NMAX
#define pb push_back
#define INF 1e9
using namespace std;

/*
 * FILES
 */
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

/*
 * DATA STRUCTURES AND VARIABLES
 */
struct Node{
    int y;
    int cost;
    Node(int y, int cost):y{y}, cost{cost} {}

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

int n, m, k;
//vector<int> holds; //strongholds
int dist[NMAX];
vector<Node>G[NMAX]; //our graph
priority_queue<Node> pq;


/*
 * Read data
 */
void read_data(){
    in >> n >> m;
    for(int i = 0; i<m; i++){
        int x, y, c;
        in >> x >> y >> c;
        G[x].pb({y, c});
    }
}

/*
 * Dijkstra's Algorithm
 */
void dijkstra(int start){
    for(int i = 0; i<=n; i++){
        dist[i] = INF;
    }
    dist[start] = 0;
    pq.push({start, dist[start]});
    while(!pq.empty()){
        auto head = pq.top();
        pq.pop();
        if(dist[head.y] != head.cost){
            continue;
        }
        int node = head.y;
        for(const auto& elem : G[node]){
            if(dist[elem.y] > dist[node] + elem.cost){
                dist[elem.y] = dist[node] + elem.cost;
                pq.push({elem.y, dist[elem.y]});
            }
        }
    }
}

int main(){

    read_data();
    dijkstra(1);
    for(int i = 2; i<=n; i++){
        dist[i] == INF ? out << 0 << ' ' : out << dist[i] << ' ';
    }
    return 0;
}