#include <fstream>
#include <iostream>
#include<set>
#include<vector>

using namespace std;

#define NM 50005
#define INF 2000000000
struct pereche
{
    int c,y;
};
int n, m, dist[NM];
vector <pereche> G[NM];
struct compara
{
    bool operator()(pereche u,pereche v)
    {
        if(u.c!=v.c)
            return u.c<v.c;
        return u.y<v.y;
    }
};
set <pereche,compara> s;
set <pereche,compara>::iterator it;

void dijkstra()
{
    int i,im;
    dist[1]=0;
    for (i=2; i<=n; i++)
        dist[i] = INF;
    s.insert({0,1});
    while (!s.empty())
    {
/*
        for(it=s.begin();it!=s.end();++it)
            cout<<"["<<it->y<<' '<<it->c<<"] ";
       cout<<endl;
*/
        pereche u,z,v;
        z=*s.begin();
        s.erase(z);
        im=z.y;
        for (i=0; i<G[im].size(); i++)
        {
            u=G[im][i];
            if (dist[im] + u.c < dist[u.y])
            {
                v.y=u.y;
                v.c=dist[u.y];
                if(s.find(v)!=s.end())
                    s.erase(s.find(v));
                dist[u.y] = dist[im] + u.c;
                v.c=dist[u.y];
                s.insert(v);
            }
        }

    }
}

int main()
{
    int i,x;
    pereche u;
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        fin >> x >> u.y >> u.c;
        G[x].push_back(u);
    }
    dijkstra();

    for (i=2; i<=n; i++)
        if(dist[i] != INF)
            fout << dist[i] << ' ';
            else fout<<0<<' ';
                return 0;
            }