#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


vector <pair <int,int> > v[50009];
int i,j,x,y,cost,start,finish,n,m,d[50010],minim,poz;
int viz[50010];
long long int nr[50009];

struct cmp
{
    bool operator() (int x,int y)
    {
        return d[x]>d[y];
    }
};

priority_queue<int,vector <int>,cmp> q;


void afis()
{
    int i;
    for(i=1;i<=n;i++)
    {
       // fout<<viz[i]<<" ";
    }
   // fout<<"\n";
}
void dij(int k)
{
    int i;
    for(i=1;i<=n;i++)
    {
        d[i]=1000000;
    }
    d[start]=0;
    nr[start]=1;


    int ok=0;
    while(ok==0)
    {
        ok=1;minim=1000000;
        poz=0;
        for(i=1;i<=n;i++)
        {
            if(d[i]<minim && viz[i]==0 )
            {
                minim=d[i];
                poz=i;
                ok=0;
            }
        }
       // fout<<poz<<" ";
        viz[poz]=1;
        for(i=0;i<v[poz].size();i++)
        {
            if(d[v[poz][i].first] > minim + v[poz][i].second )
            {
                d[v[poz][i].first] = minim + v[poz][i].second;
            }
        }
        afis();
    }
    //viz[start]=1;



}
int main()
{
    fin>>n>>m;//>>//start>>finish;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
       // fout<<x<<" "<<y<<" "<<cost<<"\n";
        v[x].push_back(make_pair(y,cost));
        //v[y].push_back(make_pair(x,cost));
    }
    start=1;
    dij(start);
    for(i=2;i<=n;i++)
    {
        if(d[i]!=1000000)
        fout<<d[i]<<" ";
        else fout<<"0 ";
    }
    //fout<<nr[finish]<<"\n";
}