#include <cstdio>
#include <vector>
#include <utility>
#include <limits.h>
using namespace std;
vector <pair<int,int> > v[50001];

int n,m;
int N;
int poz[50001],viz[50001],cost[50001];

struct heap{int v;int c;};
heap H[50001];

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

int Dad(int x)
{
    return x/2;
}
int LeftSon(int x)
{
    return 2*x;
}
int RightSon(int x)
{
    return 2*x+1;
}

void UpHeap(int k)
{
    while(k>1&&H[Dad(k)].c>H[k].c)
    {
        swap(H[Dad(k)],H[k]);
        poz[H[Dad(k)].v]=Dad(k);
        poz[H[k].v]=k;
        k=Dad(k);
    }
}

void DownHeap(int k)
{
    int son;
    do
    {
        son=0;
        if(LeftSon(k)<=N)
        {
            son=LeftSon(k);
            if(RightSon(k)<=N)
                if(H[RightSon(k)].c<H[LeftSon(k)].c)
                son=RightSon(k);
        }
        if(H[son].c>=H[k].c) son=0;
        if(son){swap(H[son],H[k]);poz[H[son].v]=son;poz[H[k].v]=k;k=son;}
    } while(son);
}

void Add(int vertex,int cost)
{
    if (poz[vertex]==0) {N++;poz[vertex]=N;H[N].v=vertex;H[N].c=cost;UpHeap(N);}
    else
    {
        int aux=poz[vertex];
        H[aux].c=cost;
        UpHeap(aux);
    }
}

void DeleteMin()
{
    swap(H[1],H[N]);
    N--;
    DownHeap(1);
}
void Citire()
 {
    int a,b,c;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
    }
 }
void Afisare()
{
    for(int i=2;i<=n;i++)fprintf(g,"%d ",cost[i]);
}

void Inchidere()
{
    fclose(f);
    fclose(g);
}

void Initializare()
{
    Add(1,0);
    viz[1]=1;
}

bool verif(int vaux,int start,int caux)
{
    return(viz[vaux]==0||cost[vaux]>cost[start]+caux);
}

void extrag(int &vaux, int &caux,int start)
{
    vaux=v[start][v[start].size()-1].first;
    caux=v[start][v[start].size()-1].second;
}

void Actualizare(int vaux,int caux,int start)
{
    Add(vaux,cost[start]+caux);
    viz[vaux]=1;
    cost[vaux]=cost[start]+caux;
}

int main()
{
    int start,vaux,caux;
    Citire();
    Initializare();
    while(N)
    {
        start=H[1].v;
        while(!v[start].empty())
        {
            extrag(vaux,caux,start);
            v[start].pop_back();
            if(verif(vaux,start,caux)) Actualizare(vaux,caux,start);
        }
        DeleteMin();
    }
    Afisare();
    Inchidere();
    return 0;
}