//vila-campion
/*#include<bits/stdc++.h>
using namespace std;

deque < pair<int,int> > Min,Max;
int ans;

int main()
{
    int n,k,i,x;
    ifstream fin("vila2.in");
    ofstream fout("vila2.out");
    fin>>n>>k;
    for(i=1;i<=k;i++)
    {
        fin>>x;
        while(!Max.empty() && Max.back().first<=x )
            Max.pop_back();
        Max.push_back(make_pair(x,i));
        while(!Min.empty() && Min.back().first>=x  )
            Min.pop_back();
        Min.push_back(make_pair(x,i));

    }

    ans=Max.front().first-Min.front().first;
    //cout<<ans;

    for(i=k+1;i<=n;i++)
    {
        fin>>x;

        if(Max.front().second<i-k)
            Max.pop_front();
        if(Min.front().second<i-k)
            Min.pop_front();
        while(!Max.empty() && Max.back().first<=x )
            Max.pop_back();
        Max.push_back(make_pair(x,i));
        while(!Min.empty() && Min.back().first>=x )
            Min.pop_back();
        Min.push_back(make_pair(x,i));
        ans=max(ans,Max.front().first-Min.front().first);

    }
    fout<<ans;
    fin.close();
    fout.close();

}*/
//deque-infoarena
/*#include<stdio.h>
int D[5000010],A[5000010];
unsigned long long s;
//creez un deque in care retin pozitiile sirului T[i], in care T[i1] este minimul cautat

int main()
{
    int i,n,k,p=1,u=0,x;
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);

    scanf("%d %d",&n,&k);

    for(i=1;i<=k;i++)
    {   scanf("%d ",&A[i] );
    //cout<<A[i];
        while(p<=u && A[D[u]]>A[i])
            u--;
        D[++u]=i;
    }
    s+=A[D[p]];
    //printf("%d",s);

    for(i=k+1;i<=n;i++)
    {
        scanf("%d ",&A[i] );
        if(D[p]==i-k) p++;
        while(p<=u && A[D[u]]>A[i])
            u--;
        D[++u]=i;
        s+=A[D[p]];
    }
    printf("%d",s);
}*/
/*#include<bits/stdc++.h>
using namespace std;

deque < pair<int,int> > Min;
long long ans;

int main()
{
    int n,k,i,x;
    ifstream fin("deque.in");
    ofstream fout("deque.out");
    fin>>n>>k;
    for(i=1;i<=k;i++)
    {
        fin>>x;
        while(!Min.empty() && Min.back().first>=x  )
            Min.pop_back();
        Min.push_back(make_pair(x,i));

    }

    ans=Min.front().first;
    //cout<<ans;

    for(i=k+1;i<=n;i++)
    {
        fin>>x;
        if(Min.front().second==i-k)
            Min.pop_front();
        while(!Min.empty() && Min.back().first>=x )
            Min.pop_back();
        Min.push_back(make_pair(x,i));
        ans+=Min.front().first;

    }
    fout<<ans;
    fin.close();
    fout.close();

}*/

/*#include<iostream>
#include<fstream>
using namespace std;

int n,tata[100001],h[100001],m;

void Union_ponderare(int x,int y)
{
    if(h[x]>h[y]) tata[y]=x;
    else
    {
        tata[x]=y;
        if(h[x]==h[y]) h[y]++;
    }
}

int Find_compresie(int x)
{
    int r=x,y=x,help;
    while(tata[r]!=r) r=tata[r];
    while(y!=r)
    {
        help=tata[y];
        tata[y]=r;
        y=help;
    }
    return r;

}

int main()
{
    int i,c,x,y;
    ifstream fin("disjoint.in");
    ofstream fout("disjoint.out");
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {tata[i]=i;
    h[i]=1;
    }
    for(i=1;i<=m;i++)
    {
        fin>>c;
        if(c==1)
        {
            fin>>x>>y;
            if(Find_compresie(x)!=Find_compresie(y))
            Union_ponderare(Find_compresie(x),Find_compresie(y));
        }
        else
        {
            fin>>x>>y;
            if(Find_compresie(x)==Find_compresie(y))
                fout<<"DA"<<'\n';
            else fout<<"NU"<<'\n';

        }
    }

}*/

#include<bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");

ofstream gout("dijkstra.out");

const int NMax=50052;

const int Dim=(1<<30);

typedef struct LM{int nod,cost;};

int d[NMax];

int n,m;

vector <int> G[NMax], C[NMax];



typedef struct cmpdst

{

    bool operator() (LM x, LM y)

    {

        return x.cost>y.cost;

    }

};



priority_queue <LM, vector<LM> , cmpdst> q;





void citire()

{   int i,x,y,z;

    fin>>n>>m;

for (i=1;i<=m;i++)

{

    fin>>x>>y>>z;

    G[x].push_back(y);

    C[x].push_back(z);



}



}





void dijkstra(int S)

{   int viz[NMax]={0},i;

    for(i=1;i<=n;i++)

        d[i]=Dim;

    d[S]=0;

    LM aux,aux2;

    aux.cost=0;

    aux.nod=S;

    q.push(aux);

    while(!q.empty())

    {

        aux=q.top();

        q.pop();

        if(viz[aux.nod]==0)

        {

            viz[aux.nod]=1;

            for(i=0;i<G[aux.nod].size();i++)

            {

               int halp;

                halp=G[aux.nod][i];

                if(d[halp]>d[aux.nod]+C[aux.nod][i])

                {

                    d[halp]=d[aux.nod]+C[aux.nod][i];

                    aux2.nod=halp;

                    aux2.cost=d[halp];

                    if(!viz[aux2.nod]) q.push(aux2);



                }

            }

        }



    }

}

void afisare()

{

    int i;

    for(i=2;i<=n;i++)

        if(d[i]!=Dim) gout<<d[i]<<' ';

    else gout<<"0 ";

}



int main()

{

    citire();

    dijkstra(1);

    afisare();

}