#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];
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);
}

int main()
{
    int a,b,c,start,vaux,caux;
    FILE *f=fopen("dijkstra.in","r");
    FILE *g=fopen("dijkstra.out","w");
    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));
 //       v[b].push_back(make_pair(a,c));
    }
    add(1,0);
    viz[1]=1;
    while(N)
    {
        start=H[1].v;
        while(!v[start].empty())
        {
            vaux=v[start][v[start].size()-1].first;
            caux=v[start][v[start].size()-1].second;
            v[start].pop_back();
            if(viz[vaux]==0||cost[vaux]>cost[start]+caux){add(vaux,cost[start]+caux);viz[vaux]=1;cost[vaux]=cost[start]+caux;}
        }
        deletemin();
    }
    for(int i=2;i<=n;i++)fprintf(g,"%d ",cost[i]);
    return 0;
}