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

#define inf 2000000000
struct sheap
{
    int val,node;
};

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

//must do
void init(vector <sheap> &heap)
{
    sheap ax;
    ax.val=-inf;
    ax.node=-1;
    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,vector <int> &vpos,int pos1,int pos2)
{
    sheap ax;
    ax=heap[pos1];
    heap[pos1]=heap[pos2];
    heap[pos2]=ax;
    int axi;
    int node1,node2;
    node1=heap[pos1].node;
    node2=heap[pos2].node;
    axi=vpos[node1];
    vpos[node1]=vpos[node2];
    vpos[node2]=axi;
}

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

    if (heap[pos]<heap[pos/2])
    {
        heapswap(heap,vpos,pos,pos/2);
        heapup(heap,vpos,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, vector <int> &vpos, 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,vpos,posdown,pos);
        heapdown(heap,vpos,posdown);
    }
}

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

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

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

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

class dijkstra
{
    private:vector <sheap> heap;
    private:vector <int> vpos;
    public:vector <int> dist;
    dijkstra(int nrnodes)
    {
        init(heap);
        for (int i=0;i<nrnodes;i++)
        {
            vpos.push_back(0);
            dist.push_back(inf);
        }
    }
    bool add_or_update(sheap upd)
    {
        if (upd.node>=vpos.size())
            return false;
        if (upd.node<0)
            return false;
        int node=upd.node;
        dist[node]=upd.val;
        if (vpos[node]==0)
            heapinsert(heap,vpos,upd);
        else
            heapupdate(heap,vpos,vpos[node],upd);
        return true;
    }
    bool topdelete()
    {
        if (heap.size()<=1)
            return false;
        heapdelete(heap,vpos,1);
        return true;
    }
    sheap top()
    {
        return heap[1];
    }
    bool empty()
    {
        if (heap.size()<=1)
            return true;
        return false;
    }
};

int n,m,i,a,b,c,to,cost,now,dnow;
sheap axs;

vector <pair <int,int> > muchii[50005];

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

    axs.val=0;
    axs.node=1;
    d.add_or_update(axs);

    while (!d.empty())
    {
        now=(d.top()).node;
        dnow=(d.top()).val;
        for (i=0;i<muchii[now].size();i++)
        {
            to=muchii[now][i].first;
            cost=muchii[now][i].second;
            if (dnow+cost<d.dist[to])
            {
                axs.node=to;
                axs.val=dnow+cost;
                d.add_or_update(axs);
            }
        }
        d.topdelete();
    }
    for (i=2;i<=n;i++)
        g<<d.dist[i]<<' ';
    return 0;
}