#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define S 50000
const int INF = 0x3f3f3f3f;

static int Dmin[S + 1];
static int inQ[S + 1];
static vector<pair<int, int> > graph[S + 1];

int main(int argc, char **argv) {
    int N, M;
    queue<int> Q;
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d\n", &N, &M);

    for (int i = 0; i < M; i++) {
        int u, v, c;
        scanf("%d %d %d\n", &u, &v, &c);
        graph[u].push_back(pair<int, int>(v, c));
    }

    memset(Dmin, INF, sizeof(Dmin));
    memset(inQ, false, sizeof(inQ));

    Dmin[1] = 0;
    Q.push(1);
    inQ[1] = true;

    while (Q.size() > 0) {
    	int cn = Q.front();
    	Q.pop();
    	inQ[cn] = false;
    	for (vector<pair<int, int> >::iterator it = graph[cn].begin(); it != graph[cn].end(); it++) {
    		if (Dmin[it->first] > Dmin[cn] + it->second) {
    			Dmin[it->first] = Dmin[cn] + it->second;
    			if (!inQ[it->first]) {
    				Q.push(it->first);
    				inQ[it->first] = true;
    			}
    		}
    	}
    }

    for (int i = 2; i <= N; i++) {
    	printf("%d ", Dmin[i]);
    }

    return 0;
}