#include<bits/stdc++.h>
using namespace std;

const int N_MAX = 50005;
const int oo = 0x3f3f3f3f;

typedef pair<int, int> Edge;

vector<Edge>G[N_MAX];
set< Edge >H;
int N, M;

void read()
{
    FILE *in = fopen("dijkstra.in", "r");
    fscanf(in, "%d%d", &N, &M);
    while(M--)
    {
        int x, y, c;
        fscanf(in, "%d%d%d", &x, &y, &c);
        G[x].emplace_back(y, c);
    }
}

void solve()
{
    int dist[N_MAX];

    memset(dist, oo, sizeof(dist));
    dist[1] = 0;
    H.insert(make_pair(0, 1)); // c n

    while(!H.empty())
    {
        int node = H.begin()->second;
        int cost = H.begin()->first;

        H.erase(H.begin());

        for(auto &son : G[node]){
            int to = son.first;
            int sonCost = son.second;

            if( dist[to] > dist[node] + sonCost )
            {
               if( dist[to] != oo )
                    H.erase(H.find(make_pair(dist[to], to)));
               dist[to] = dist[node] + sonCost;
               H.insert(make_pair(dist[to], to));
            }
        }
    }


    FILE *out = fopen("dijkstra.out", "w");

    for(int i = 2; i <= N; i ++){
        if( dist[i] == oo ) dist[i] = 0;
        fprintf(out, "%d ", dist[i]);
    }

}

int main()
{
    read();
    solve();
    return 0;
}