#include <cstdio>
#include <list>
#include <queue>
using namespace std;

struct edge{

    int v, weight;

    edge(int _v, int _w){
        v = _v;
        weight = _w;
    }
};

struct Compare{
    bool operator()(const int &A, const int &B){
        return A > B;
    }
};

int vertices, edges, u, v, weight;
int dist[50001];
int visited[50001];
bool inQueue[50001];
const int infinity = 25000001;
list<edge> adj[50001];

void Dijkstra(int source){

    for(int node = 1; node <= vertices; node++){
        dist[node] = infinity;
    }dist[source] = 0;

    priority_queue<int, vector<int>, Compare> PQ;
    PQ.push(source);

    while(!PQ.empty()){

        int u = PQ.top(); PQ.pop();
        inQueue[u] = false;

        for(list<edge>::iterator it = adj[u].begin(); it != adj[u].end(); it++){

            int v = it -> v;
            int weight = it -> weight;

            if(visited[v] == false || dist[u] + weight < dist[v]){

                dist[v] = dist[u] + weight;
                visited[v]++;

                if(inQueue[v] == false){
                    inQueue[v] = true;
                    PQ.push(v);
                }
            }
        }
    }
}

int main(){

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d", &vertices, &edges);

    for(int i = 1; i <= edges; i++){
        scanf("%d %d %d", &u, &v, &weight);
        adj[u].push_back(edge(v, weight));
    }Dijkstra(1);

    for(int node = 2; node <= vertices; node++){
        printf("%d ", (dist[node] == infinity) ? 0 : dist[node]);
    }
    return 0;
}