#include <iostream>
#include <vector>

#define IN "dijkstra.in", "r"
#define OUT "dijkstra.out", "w"

#define NMAX 50001
#define INF NMAX*1000

using namespace std;

struct Edge {
    int x, y, weight;
    Edge(int x=0, int y=0, int weight=0):x(x), y(y), weight(weight) {};
};

struct E {
    int y, c;
    E(int y=0, int c=0):y(y), c(c) {};
};

vector<Edge> Muchii[NMAX];
vector<E> G[NMAX];
int dist[NMAX], N, M;
bool visited[NMAX];

int cost(int x, int y) {
    for(int i=0; i<G[x].size(); ++i)
        if(G[x][i].y==y)
            return G[x][i].c;
    return INF;
}

void Dijkstra(int Start) {
    int k=1, ck;
    int minimum=INF;
    for(int i=1; i<=N; ++i) {
        int x=cost(Start, i);
        if(i!=Start&&minimum>x) {
            minimum=x;
            k=i;
        }
        dist[i]=x;
        visited[i]=0;
    }
    visited[Start]=1;
    while(1) {
        if(minimum^INF) {
            minimum=INF;
            visited[k]=1;
            for(int i=2; i<=N; ++i) {
                int x=cost(k, i);
                if(!visited[i]&&dist[i]>x+dist[k]) {
                    dist[i]=x+dist[k];
                }
                if(!visited[i]&&minimum>dist[i]) {
                    minimum=dist[i];
                    ck=i;
                }
            }
            k=ck;
        } else
            break;
    }
}

int main() {
    freopen(IN, stdin);
    freopen(OUT, stdout);
    scanf("%d%d", &N, &M);
    int x, y, c;
    for(int i=1; i<=M; ++i) {
        scanf("%d%d%d", &x, &y, &c);
        G[x].push_back(E(y, c));
    }
    Dijkstra(1);
    for(int i=2; i<=N; ++i) {
        cout<<dist[i]<<' ';
    }
    return 0;
}