#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define inf 2000000000
struct sheap
{
    int val;
    int node;
} ax,now;
int vpos[50005];

bool operator < (sheap a,sheap b)
{
    if (a.val<b.val)
        return true;
    return false;
}

vector <sheap> heap;

//must do
void init(vector <sheap> &heap)
{
    sheap ax;
    ax.val=-inf;
    heap.push_back(ax);
}

bool safe(vector <sheap> &heap,int pos)
{
    if (pos>=heap.size())
        return false;
    if (pos<=0)
        return false;
    return true;
}

void heapswap(vector <sheap> &heap,int pos1,int pos2)
{
    sheap ax;
    ax=heap[pos1];
    heap[pos1]=heap[pos2];
    heap[pos2]=ax;
    int node1,node2;
    node1=heap[pos1].node;
    node2=heap[pos2].node;
    int axi;
    axi=vpos[node1];
    vpos[node1]=vpos[node2];
    vpos[node2]=axi;
}

void heapup(vector <sheap> &heap,int pos)
{
    if (!safe(heap,pos))
        return;

    if (heap[pos]<heap[pos/2])
    {
        heapswap(heap,pos,pos/2);
        heapup(heap,pos/2);
    }
}

int heapmin(vector <sheap> &heap, int pos1, int pos2)
{
    if (heap[pos1]<heap[pos2])
        return pos1;
    return pos2;
}

void heapdown(vector <sheap> &heap, int pos)
{
    if (!safe(heap,pos*2))
        return;

    int posdown;

    if (!safe(heap,pos*2+1))
        posdown=pos*2;
    else
        posdown=heapmin(heap,pos*2,pos*2+1);

    if (heap[posdown]<heap[pos])
    {
        heapswap(heap,posdown,pos);
        heapdown(heap,posdown);
    }
}

void heapinsert(vector <sheap> &heap,sheap val)
{
    heap.push_back(val);
    int pos=heap.size()-1;
    vpos[val.node]=pos;
    heapup(heap,pos);
}

//delete last one
void heapdelete(vector <sheap> &heap)
{
    sheap last=heap[heap.size()-1];
    vpos[last.node]=0;
    heap.pop_back();
}

void heapdelete(vector <sheap> &heap,int pos)
{
    if (!safe(heap,pos))
        return;
    int last=heap.size()-1;
    heapswap(heap,pos,last);
    heapdelete(heap);
    if (!safe(heap,pos))
        return;
    heapup(heap,pos);
    heapdown(heap,pos);
}

void heapupdate(vector <sheap> &heap, int pos, sheap arg)
{
    heap[pos]=arg;
    heapup(heap,pos);
    heapdown(heap,pos);
}


vector <pair <int,int> > muchii[500005];
int n,m,i,a,b,c,nownode,nowval,dist[500005],tonode,todist;

int main(void)
{
    init(heap);
    FILE * f;
    f=fopen("dijkstra.in","r");
    ofstream g("dijkstra.out");
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        muchii[a].push_back(make_pair(b,c));
    }

    for (i=1;i<=n;i++)
        dist[i]=inf;

    ax.val=0;
    ax.node=1;
    dist[1]=0;
    heapinsert(heap,ax);
    while (heap.size()>1)
    {
        now=heap[1];
        nownode=now.node;
        nowval=now.val;
        for (i=0;i<muchii[nownode].size();i++)
        {
            tonode=muchii[nownode][i].first;
            todist=muchii[nownode][i].second;
            if (nowval+todist<dist[tonode])
            {
                ax.val=nowval+todist;
                ax.node=tonode;
                dist[tonode]=ax.val;
                if (vpos[tonode]!=0)
                    heapupdate(heap,vpos[tonode],ax);
                else
                    heapinsert(heap,ax);
            }
        }
        heapdelete(heap,1);
    }
    for (i=2;i<=n;i++)
        g<<dist[i]<<' ';
    return 0;
}