#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream gout("dijkstra.out");
const int NMax=50000;
const int Dim=(1<<27);
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],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];
                    q.push(aux2);

                }
            }
        }

    }
}
void afisare()
{
    int i;
    for(i=2;i<=n;i++)
        if(d[i]!=NMax)
        gout<<d[i]<<' ';
    else gout<<0<<' ';
}

int main()
{
    citire();
    dijkstra(1);
    afisare();
}