#include <iostream>
#include <fstream>
#include <vector>
#define infinit 1000000001

using namespace std;

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

struct muchie
{
    int nod,cost;
};

vector <muchie> a[50001];
int d[50001],viz[50001];

int main()
{int n,m,i,j,nod,nod2,cost,s,pmin;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>nod>>nod2>>cost;
        a[nod].push_back({nod2,cost});
    }
    s=1;
    for(i=1;i<=n;i++)
    {
        d[i]=infinit;
    }
    for(i=0;i<a[s].size();i++)
    {
        nod=a[s][i].nod;
        d[nod]=a[s][i].cost;
    }
    d[0]=infinit;
    d[s]=0;
    viz[s]=1;
    for(i=1;i<n;i++)
    {
        pmin=0;
        for(j=1;j<=n;j++)
        {
            if(viz[j]==0&&d[j]<d[pmin])
            {
                pmin=j;
            }
        }
        if(pmin>0)
        {
            viz[pmin]=1;
            for(j=0;j<a[pmin].size();j++)
            {
                nod=a[pmin][j].nod;
                cost=a[pmin][j].cost;
                if(viz[nod]==0&&d[nod]>cost+d[pmin])
                {
                    d[nod]=cost+d[pmin];
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(d[i]==infinit)
        {
            d[i]=0;
        }
    }
    for(i=2;i<=n;i++)
    {
        g<<d[i]<<" ";
    }
    return 0;
}