#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int maxn = 50001;
const int inf = 1 << 30;
struct vect{ int nod,cost; vect *urm;} *A[maxn];
int n,m,k,NC;
vector <int> D;
vector <unsigned short> H,P;
void Adaug(int NC, int Nod, int Cost) { vect *aux = new vect; aux -> nod = Nod; aux -> cost = Cost; aux -> urm = A[NC]; A[NC] = aux; }
void Citire()
{
    int x,y,z;
    cin>>n>>m;
    while(m) cin>>x>>y>>z,Adaug(x,y,z),m--;
    D.resize(n+1); H.resize(n+1); P.resize(n+1); D.assign(n+1,inf); P.assign(n+1,0);
    D[1]=0;
}
void Afisare()
{
    for(int i=2;i<=n;i++)
        if(D[i]==inf) cout<<"0 ";
        else cout<<D[i]<<' ';
}
void RearanjareHeap()
{
    int NS = 1, fiu, aux;
    while((NS<<1) <= k)
    {
        fiu = NS << 1;
        if(fiu+1 <= k && D[H[fiu]] > D[H[fiu+1]]) fiu++;
        if(D[H[fiu]] < D[H[NS]])
        {
            P[H[fiu]] = NS; P[H[NS]] = fiu;
            aux = H[fiu], H[fiu] = H[NS], H[NS] = aux;
            NS = fiu;
        }
        else return;
    }
}
void AddHeap(int NS)
{
    int tata, aux;
    while(NS > 1 && D[H[(NS>>1)]] > D[H[NS]])
    {
        tata = NS >> 1;
        P[H[tata]] = NS; P[H[NS]] = tata;
        aux = H[tata], H[tata] = H[NS], H[NS] = aux;
        NS = tata;
    }
}
void DijkstraCuHip(int NS)
{
    H[++k] = NS;
    P[NS] = k;
    while(k)
    {
        NC = H[1];
        H[1] = H[k--];
        P[H[1]]=1;
        RearanjareHeap();
        while(A[NC])
        {
            if(D[A[NC]->nod] > D[NC] + A[NC]->cost)
            {
                D[A[NC]->nod] = D[NC] + A[NC]->cost;
                if(P[A[NC]->nod]) AddHeap(P[A[NC]->nod]);
                else H[++k] = A[NC] -> nod, P[A[NC]->nod] = k, AddHeap(P[A[NC]->nod]);
            }
            A[NC] = A[NC] -> urm;
        }
    }
}
int main()
{
    Citire();
    DijkstraCuHip(1);
    Afisare();
}