#include<fstream>
#include<vector>
#include<queue>
#include<limits.h>

using namespace std;

vector<vector<pair<int,int>>>v;
priority_queue<pair<int,int>>q;
vector<int>cost;
vector<bool>ap;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

void solve()
{
    while(!q.empty())
    {
        pair<int,int> x = q.top();
        q.pop();
        if(x.first == cost[x.second])
        {
            for(auto& it : v[x.second])
            {
                if(cost[it.first] < x.first + it.second)
                {
                    cost[it.first] = x.first + it.second;

                    q.push({cost[it.first], it.first});
                }
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    ap.resize(n);
    cost.resize(n, INT_MIN);
    v.resize(n);
    for(int i = 0; i < m; i++)
    {
        int V1, V2, C;
        cin >> V1 >> V2 >> C;
        V1--, V2--;
        v[V1].push_back({V2, -C});
    }
    cost[0] = 0;
    q.push({0, 0});
    solve();
    ap[0] = true;
    for(int i = 1; i < n; i ++)
    {
        if(cost[i] == INT_MIN)
        {
            cout << 0 << " ";
        }
        else
        cout << -cost[i] << " ";
    }
    return false;
}