#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>

#define NMAX 50001
#define MMAX 250001
#define INF 9999999

using namespace std;

vector<pair<int, int> > adjList[NMAX];
int dist[NMAX];
bool visited[NMAX];
int n, m;
queue<int> q;
int nodes[NMAX];

void bellmanFord(int source) {

	for (int i = 1; i <= n; ++i) {
		dist[i] = INF;
	}
	
	visited[source] = true;
    dist[source] = 0;
    q.push(source);
 
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        visited[node] = false;
 
        for (int i = 0; i < adjList[node].size(); ++i) {
        	pair<int, int> aux = adjList[node][i];
            if (dist[node] < INF) {
            	int alt = dist[node] + aux.second;
                if (dist[aux.first] > alt) {
                    dist[aux.first] = alt;
                    if (!visited[aux.first]) {
                        q.push(aux.first);
                        visited[aux.first] = true;
                        nodes[aux.first] ++;
                    }
                }
            }
        }
    }
}

int main() {
	FILE *in, *out;
	in = fopen("dijkstra.in", "r");
	out = fopen("dijkstra.out", "w");
	int a, b, l;
	fscanf(in, "%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		fscanf(in, "%d%d%d", &a, &b, &l);
		adjList[a].push_back(make_pair(b, l));
	}
	bellmanFord(1);
	for (int i = 2; i <= n; ++i) {
		if (dist[i] != INF) {
			fprintf(out, "%d ", dist[i]);
		} else {
			fprintf(out, "0 ");
		}
	}
	return 0;
}