#include<fstream>
#include<queue>
#include<vector>

#define MAXN 50001
#define INF 20000001

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


struct Edge {
    int n, c;
    Edge(int a, int b) {n = a; c = b;}
    Edge() {}
    const bool operator <(const Edge &a) const {return c>a.c;}
};

vector <Edge> G[MAXN];
int SOL[MAXN], PARENT[MAXN];
bool PR[MAXN];
int n, m;

void citire() {
    fin>>n>>m;
    int a, b, c;
    for(int i=1; i<=m; i++) {
        fin>>a>>b>>c;
        SOL[a] = INF;
        SOL[b] = INF;
        G[a].push_back(Edge(b, c));
        //G[b].push_back(Edge(a, c));
    }
}


void dijkstra(int start) {
    PARENT[start] = -1;
    SOL[start] = 0;
    priority_queue<Edge> Q;
    Q.push(Edge(start, 0));
    while(!Q.empty()) {
        Edge e = Q.top();
        Q.pop();
        if(PR[e.n]) continue;
        else PR[e.n] = true;
        int node = e.n;
        for(int i=0; i<G[node].size(); i++) {
            Edge edge = G[node][i];
            if(SOL[edge.n] > SOL[node] + edge.c) {
                SOL[edge.n] = SOL[node] + edge.c;
                Q.push(Edge(edge.n, SOL[edge.n]));
            }
        }
    }
}

int main() {
    citire();
    dijkstra(1);
    for(int i=2; i<=n; i++) {
        if(SOL[i] < INF)
            fout<<SOL[i]<<" ";
        else fout<<0<<" ";
    }
    return 0;
}