#include <fstream>
#include <queue>
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
vector <pair <int,int> >lista[50010];
priority_queue <pair <int,int> > d;
int dist[50001],viz[50001];
void dijkstra()
{
    int nod1,nod2,cost,i;
    d.push({0,1});
    dist[1]=0;
    while (d.size()>0)
    {
        nod1=d.top().second;
        d.pop();
        if (viz[nod1]==0)
        {
            viz[nod1]=1;
            for (i=0; i<lista[nod1].size(); i++)
            {
                nod2=lista[nod1][i].first;
                cost=lista[nod1][i].second;
                if (dist[nod1]+cost<dist[nod2])
                {
                    ///sef[nod2]=sef[nod1];
                    dist[nod2]=dist[nod1]+cost;
                    d.push({-dist[nod2],nod2});
                }
                /*else
                    if (dist[nod1]+cost==dist[nod2])
                        if (sef[nod2]>sef[nod1])
                            sef[nod2]=sef[nod1];*/
            }
        }
    }
}
int main()
{
    int n,m,k,i,s,x,y,z;
    cin>>n>>m;
    for (i=1; i<=n; i++)
        dist[i]=1000000000;

    for (i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        lista[x].push_back({y,z});
        ///lista[y].push_back({x,z});
    }
    dijkstra();
    for(i=2;i<=n;i++)
        if(dist[i]!=1000000000)
            cout<<dist[i]<<" ";
        else
            cout<<"0 ";
    return 0;
}