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

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define nmax 50005

int n,m,x,y,cost,d[nmax],i,nod,vizitat[nmax];
vector <int> arc[nmax];
vector <int> costul[nmax];
queue <int> q;

void bfs()
{
    q.push(1);
    vizitat[1]=0;
    d[1]=0;
    while(q.empty()!=1)
    {

        nod=q.front();
        vizitat[nod]=0;
        q.pop();
        for(int i=0;i<arc[nod].size();i++)
        {
            if(d[arc[nod][i]]>d[nod]+costul[nod][i])
            {
                d[arc[nod][i]]=d[nod]+costul[nod][i];
                if(vizitat[arc[nod][i]]==0)
                {
                    q.push(arc[nod][i]);
                    vizitat[arc[nod][i]]=1;
                }
            }
        }
    }
}

int main()
{
    f>>n>>m;
    while(m>0)
    {
        f>>x>>y>>cost;
        arc[x].push_back(y);
        costul[x].push_back(cost);
        m--;
    }
    for(i=1; i<=n ; i++)
        d[i]=2000000001;

    bfs();

    for(i=1;i<n;i++)
        if(d[i+1]==2000000001)
            g<<0<<" ";
        else g<<d[i+1]<<" ";

    f.close();
    g.close();
    return 0;
}