#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <iomanip>
#include <bitset>

#define szybcior ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
const ll inf = 10e17;
const ll ile = 300090;
vector<pair<ll,ll>> v[ile];
vector<bool> bo(ile, 0);
ll dist[ile];
ll n,m;

inline void init()
{

    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        ll a,b,c;
        cin >> a >> b >> c;
        v[a].push_back({b,c});
        // v[b].push_back({a,c});
    }

    for(int i = 0; i <= n + 1; i++)
        dist[i] = inf;
}

inline void dijkstra(ll start)
{
    priority_queue<ll, std::vector<ll>, std::greater<ll> > pq;
    pq.push(start);
    dist[start] = 0;
    while(!pq.empty())
    {
        ll node = pq.top();
        pq.pop();
        for(auto it: v[node])
        {
            if(!bo[it.first])
            {
                bo[it.first] = true;

                if(dist[it.first] > dist[node] + it.second)
                    dist[it.first] = dist[node] + it.second, pq.push(it.first);

            }

        }
    }
}
int main()
{
    szybcior;
    init();
    dijkstra(1);
    // cout << "\n";

    for(ll i = 1; i <= n; i++)
    {
        if(dist[i] != inf)
            cout << dist[i] << " ";
        else
            cout << "-1 ";
    }
    return 0;
}