#include <bits/stdc++.h>
#define nmax 50001
#define inf INT_MAX

using namespace std;
vector <pair <int, int> > v[nmax];
vector <int> cost (nmax, inf);
int viz[nmax];
set <pair <int, int> >q;
int main()
{

    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n, m, a, b, c, i, j;
    f >> n >> m;
    for (i=1;i<=m;++i)
    {
        f >> a >> b >> c;
        v[a].push_back(make_pair(b,c));

    }
    q.insert(make_pair(0,1));
    cost[1]=0;
    while(!q.empty())
    {
        pair <int, int> tmp = *(q.begin());
        q.erase(q.begin());
        i=tmp.second;

        vector < pair <int, int> > :: iterator it;
        for (it=v[i].begin();it!=v[i].end();++it)
        {
            if (i==1) cout << (*it).first << " ";
            int v=(*it).first;
            int k=(*it).second;
            if (cost[v]>cost[i]+k)
            {

                if (cost[v]!=inf)
                q.erase(q.find(make_pair(cost[v],v)));
            cost[v]=cost[i] + k;
            q.insert(make_pair(cost[v],v));
            }

        }

    }
    for (i=2;i<=n;++i)
        if (cost[i]!=inf) g << cost[i] << " ";
    else g << 0 << " ";


    return 0;
}