#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 9999999
#define rc(s) return cout << s,0
#define fast ios_base::sync_with_stdio(false);cin.tie(0)
#define endl '\n'
#define cin fin
#define cout fout
using namespace std;

vector< pair<int,int> > vec[maxn];
ll dist[maxn];
ll T,src,n,m,x,y,cst,i;
priority_queue< pair<ll,ll> , vector < pair<ll,ll> >,greater< pair<ll,ll> > > Q;
void Dijkstra(ll nod)
{
    memset(dist,-1,sizeof(dist));
    dist[nod] = 0;
    Q.push(make_pair(dist[nod],nod));
    while(!Q.empty())
    {
        int u = Q.top().second;
        Q.pop();
        for(ll i = 0;i<vec[u].size();i++)
        {
            if(dist[vec[u][i].second]==-1 || dist[vec[u][i].second]>dist[u]+vec[u][i].first)
            {
                dist[vec[u][i].second] = dist[u]+vec[u][i].first;
                Q.push(make_pair(dist[vec[u][i].second],vec[u][i].second));
            }
        }
    }
}


int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    cin >> n >> m;
    for(ll i = 1;i<=m;i++)
    {
        cin >> x >> y >> cst;
        vec[x].push_back(make_pair(cst,y));
    }
    Dijkstra(1);
    for(i = 2;i<=n;i++) cout << dist[i] << ' ';
    fin.close();
    fout.close();
}