#include <fstream>
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;};
vect *A[maxn];
int n,m,p,x,y,z,D[maxn],H[maxn],P[maxn],k,NC;
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()
{
    cin>>n>>m;
    while(m) cin>>x>>y>>z,Adaug(x,y,z),m--;
}
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)
{
    for(int i = 2; i <= n; i++) D[i] = inf;
    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();
}