#include <bits/stdc++.h>
#include <cstdio>
#include <queue>

using  namespace std;

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

#define inf 1000000000

int n, m;
//// node val
vector<pair<long long,int>> adj[6];

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c; 
        adj[x].push_back({y, c});
    }

    bitset<6> viz;
    priority_queue<pair<int, int>> pq;

    vector<long long> dist(n + 1, inf);

    pq.push({1, 0});
    dist[1] = 0;

    while(!pq.empty())
    {
        int a = pq.top().first; pq.pop();
        if(viz[a]) continue;
        viz[a] = 1;
        for(auto x : adj[a])
        {
            int b = x.first, w = x.second;
            if(dist[a] + w < dist[b])
            {
                dist[b] = dist[a] + w;
                pq.push({-dist[b], b});
            }
        }
    }

    for(int i = 1; i <= n; i++)
    {
        fout << dist[i] << ' ';
    }
}