#include <fstream>
#include <queue>
#include <string.h>

using namespace std;
const int Nmax = 50005;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

vector<pii> G[Nmax];
queue<int> Q;

int dist[Nmax];
int inQueue[Nmax];

int main()
{
    ifstream f ("dijkstra.in");
    ofstream g ("dijkstra.out");

    int N, M, a, b, w;
    f >> N >> M;
    
    memset(dist, INF, sizeof(dist));
    memset(inQueue, 0, sizeof(inQueue));

    for (int e = 0; e < M; e++) {
        f >> a >> b >> w;
        G[a-1].push_back(make_pair(b-1, w));
    }
    
    dist[0] = 0;
    inQueue[0] = 1;
    Q.push(0);

    while (!Q.empty()) {
        int a = Q.front(); Q.pop();
        inQueue[a] = 0;
        for (auto x: G[a]) {
            if (dist[x.first] > dist[a] + x.second) {
                dist[x.first] = dist[a] + x.second;
                if (!inQueue[x.first]) {
                    inQueue[x.first] = 1;
                    Q.push(x.first);
                }
            }
        }
    }
    for (int i = 1; i < N; i++)
        g << (dist[i] == INF ? 0 : dist[i]) << ' ';
    g << '\n';

    return 0;
}