#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 50001;
const long long INF = 5000000000;

struct Edge{
    int x, y;
    long long c;
};

vector < Edge > edges;
int N, M;

void read(){
    fin >> N >> M;
    for(int i = 0; i < M; i++){
        Edge e;
        fin >> e.x >> e.y >> e.c;
        edges.push_back(e);
    }
}

long long dist[NMAX];
void init(){
    for(int i = 1; i <= N; i++){
        dist[i] = INF;
    }
    dist[1] = 0;
}

void relax(Edge edge){
    if(dist[edge.y] > dist[edge.x] + edge.c){
        dist[edge.y] = dist[edge.x] + edge.c;
    }
}

void bellman_ford_brutus(){
    init();
    for(int i = 1; i < N; i++){
        for(Edge edge: edges){
            relax(edge);
        }
    }
}

int main()
{
    read();
    bellman_ford_brutus();
    for(int i = 2; i <= N; i++){
        if(dist[i] == INF){
            fout << 0 << " ";
        }else{
            fout << dist[i] << " ";
        }

    }
    return 0;
}