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

using namespace std;

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

const int NMAX = 50001;
const int inf = 0x3f3f3f3f;

struct Edge{
    int x, y, 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);
    }
}

int 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++){
        fout << dist[i] << " ";
    }
    return 0;
}