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

const int inf = 1 << 30;
int n,m,p,x,y,z;
int dist[50001];
unsigned short Heap[50001],Pozitie[50001];
bool Vizitat[50001];
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();
        vect *aux = A[NodCurent];
        while(aux)
        {
            if(!Vizitat[aux->nod])
                if(dist[aux->nod] > dist[NodCurent] + aux->cost)
                {
                    dist[aux->nod] = dist[NodCurent] + aux->cost;
                    if(Pozitie[aux->nod]) AddHeap(Pozitie[aux->nod]);
                    else
                    {
                        Heap[++ElementeHeap] = aux -> nod;
                        Pozitie[aux->nod] = ElementeHeap;
                        AddHeap(Pozitie[aux->nod]);
                    }
                }
            aux = aux -> urm;
        }
    }
}
int main()
{
    Citire();
    DijkstraCuHip(p);
    Afisare();
}