#include <fstream>
#include <queue>
using namespace std;

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

#define int long long

int dist[50005];
vector<vector<pair<int,int>>>v(50005);

int32_t main()
{
    int n,m;
    cin>>n>>m;
    for (int i=2; i<=n; i++) dist[i]=-1;
    for (int i=1; i<=m; i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        pair<int,int>r;
        r.first=y;
        r.second=w;
        v[x].push_back(r);
    }
    priority_queue<pair<int,int>>pq;
    pair<int,int>r;
    r.first=0;
    r.second=1;
    pq.push(r);
    while (pq.empty()==0)
    {
        int dc=-pq.top().first,nd=pq.top().second;
        pq.pop();
        if (dc==dist[nd])
        {
            for (int i=0; i<v[nd].size(); i++)
            {
                if (dist[v[nd][i].first]<0||(dc+v[nd][i].second<dist[v[nd][i].first]))
                {
                    pair<int,int>r;
                    dist[v[nd][i].first]=dc+v[nd][i].second;
                    r.first=-dist[v[nd][i].first];
                    r.second=v[nd][i].first;
                    pq.push(r);
                }
            }
        }
    }
    for (int i=2; i<=n; i++)
    {
        if (dist[i]<0) cout<<"0 ";
        else cout<<dist[i]<<" ";
    }
}
/*
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6*/