#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
#define ll long long
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
vector<vector<pair<ll, ll>>> v(50005);
vector<ll> dmin(500005, 1e15);
int main()
{
    ll n, m, x, y, z;
    cin>>n>>m;
    pq.push({1, 0});
    dmin[1] = 0;
    for(int i = 1; i <= m; i++)
    {
        cin>>x>>y>>z;
        v[x].push_back({y, z});
    }
    while(!pq.empty())
    {
        if(pq.top().second < dmin[pq.top().first])
            {pq.pop(); continue;}
        for(int i = 0; i < v[pq.top().first].size(); i++)
            if(dmin[v[pq.top().first][i].first] > v[pq.top().first][i].second + dmin[pq.top().first])
                dmin[v[pq.top().first][i].first] = v[pq.top().first][i].second + dmin[pq.top().first], pq.push({v[pq.top().first][i].first, dmin[v[pq.top().first][i].first]});
        pq.pop();
    }
    for(int i = 2; i <= n; i++)
    {
        if(dmin[i] == 1e15)
            cout<<"0"<<" ";
        else
            cout<<dmin[i]<<" ";
    }
    return 0;
}