#include <iostream>
#include <fstream>
#include <vector>
#define grup pair<int,int>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int DIM=200000,inf=1<<30;
vector< pair<int,int> > v[DIM];
int N,M,d[DIM],j,k,poz[DIM],H[DIM],f;
void citire()
{
    int x,y,z;
    fin>>N>>M;
    while(M--)
    {
        fin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
}
void schimbare(int a,int b)
{
    swap(H[a],H[b]);
    swap(poz[H[a]],poz[H[b]]);
}
void urca(int k)
{
    while(d[H[k]]<d[H[k/2]] && k>1)
        schimbare(k,k/2);
}
void coboara(int k)
{
    int ok=1;
    while(k<=f/2 && ok)
    {
        ok=0;
        if(k*2+1<=f && d[H[k*2+1]]<d[H[k*2]] && d[H[k*2+1]]<d[H[k]])
            schimbare(k*2+1,k),ok=1,k=k*2+1;
        else if(d[H[k*2]]<d[H[k]])
            schimbare(k*2,k),ok=1,k=k*2;
    }
}
void dijkstra()
{
    for(int i=2;i<=N;++i)
        d[i]=inf,poz[i]=-1;
    H[++f]=1;
    poz[H[1]]=1;
    while(f>0)
    {
        int min=inf,pmin;
        vector< grup >::iterator it=v[H[1]].begin();
        min=1,pmin=H[1];
        schimbare(min,f);
        f--;
        coboara(1);
        while(it!=v[pmin].end())
        {
            if(d[it->first]>d[pmin]+it->second)
            {
                d[it->first]=d[pmin]+it->second;
                if(poz[it->first]!=-1)
                    urca(poz[it->first]);
                else
                {
                    H[++f]=it->first;
                    poz[it->first]=f;
                    urca(f);
                }
            }
            it++;
        }
    }
}
void afisare()
{
    for(int i=2;i<=N;++i)
        if(d[i]!=inf)
            fout<<d[i]<<" ";
        else
            fout<<0<<" ";

}
int main()
{

    citire();
    dijkstra();
    afisare();
    return 0;
}