#include <fstream>
#include <bitset>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int maxn = 50001;
struct vect{ int32_t nod; uint16_t cost; vect *urm;};
vect *A[maxn] = {NULL};

const int inf = 1 << 30;
int32_t n,m,p,x,y,z;
int32_t dist[maxn];
uint16_t Heap[maxn],Pozitie[maxn];
bitset <maxn>Vizitat;
int ElementeHeap,NodCurent;

void Adaug(int NodCurent, int Nod, int Cost)
{
    vect *aux = new vect;
    aux -> nod = Nod;
    aux -> cost = Cost;
    aux -> urm = A[NodCurent];
    A[NodCurent] = aux;
}
void Citire()
{
    cin>>n>>m; p=1;
    while(m) cin>>x>>y>>z,Adaug(x,y,z),m--;
}
void Afisare()
{
    for(int i=2;i<=n;i++)
        if(dist[i]==inf) cout<<"0 ";
        else cout<<dist[i]<<' ';
}
void RearanjareHeap()
{
    int NodStart = 1, fiu, aux;
    while(NodStart < ElementeHeap)
    {
        fiu = NodStart << 1;
        if(fiu <= ElementeHeap)
        {
            if(fiu+1 <= ElementeHeap && dist[Heap[fiu]] > dist[Heap[fiu+1]]) fiu++;
            if(dist[Heap[fiu]] < dist[Heap[NodStart]])
            {
                Pozitie[Heap[fiu]] = NodStart;
                Pozitie[Heap[NodStart]] = fiu;
                aux = Heap[fiu], Heap[fiu] = Heap[NodStart], Heap[NodStart] = aux;
                NodStart = fiu;
            }
            else return;
        }
        else return;
    }
}
void AddHeap(int NodStart)
{
    int tata, aux;
    while(NodStart > 1)
    {
        tata = NodStart >> 1;
        if(dist[Heap[tata]] > dist[Heap[NodStart]])
        {
            Pozitie[Heap[tata]] = NodStart;
            Pozitie[Heap[NodStart]] = tata;
            aux = Heap[tata], Heap[tata] = Heap[NodStart], Heap[NodStart] = aux;
            NodStart = tata;
        }
        else return;
    }
}
void DijkstraCuHip(int NodStart)
{
    for(int i = 1; i <= n; i++) dist[i] = inf;
    dist[NodStart] = 0;
    Heap[++ElementeHeap] = NodStart;
    Pozitie[NodStart] = ElementeHeap;

    while(ElementeHeap)
    {
        NodCurent =  Heap[1];
        Heap[1] = Heap[ElementeHeap];
        ElementeHeap--;
        Pozitie[Heap[1]]=1;
        RearanjareHeap();
        while(A[NodCurent])
        {
            if(!Vizitat[A[NodCurent]->nod])
                if(dist[A[NodCurent]->nod] > dist[NodCurent] + A[NodCurent]->cost)
                {
                    dist[A[NodCurent]->nod] = dist[NodCurent] + A[NodCurent]->cost;
                    if(Pozitie[A[NodCurent]->nod]) AddHeap(Pozitie[A[NodCurent]->nod]);
                    else
                    {
                        Heap[++ElementeHeap] = A[NodCurent] -> nod;
                        Pozitie[A[NodCurent]->nod] = ElementeHeap;
                        AddHeap(Pozitie[A[NodCurent]->nod]);
                    }
                }
            A[NodCurent] = A[NodCurent] -> urm;
        }
    }
}
int main()
{
    Citire();
    DijkstraCuHip(p);
    Afisare();
}