#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50003
#define inf 1<<19
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,d[Nmax];
bool verif[Nmax];
vector <pair<int ,int> > v[Nmax];
priority_queue< pair<int,int>, vector < pair<int,int> > ,greater <pair<int,int> > > q;
int main()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        v[x].push_back(make_pair(cost,y));
    }
    for (int i=2;i<=n;i++)
        d[i]=inf;
    q.push(make_pair(0,1));
    while (!q.empty())
    {
        int cost=q.top().first;
        int nod=q.top().second;
        q.pop();
        if (verif[nod])
            continue;
        verif[nod]=true;
        for (vector < pair <int,int> >::iterator it=v[nod].begin();it!=v[nod].end();it++)
        {
            int nodn=(*it).second;
            int costn=(*it).first;
            if (d[nodn]>costn+cost)
            {
                d[nodn]=cost+costn;
                q.push(make_pair(d[nodn],nodn));

            }


        }


    }
    for (int i=2;i<=n;i++)
    {
        if (d[i]==inf)
            fout<<0<<' ';
        else
            fout<<d[i]<<' ';
    }
    return 0;
}