#include <fstream>
#define dim 50001
#define INF 1 << 28
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int d[dim],heap[dim],poz[dim],cost,i,j,k,nxt,node,a,b,c,n,m;
bool viz[dim];
vector < pair <int,int> > G[dim];
void downDate(int pozi)
{
    int po;
    while(pozi*2<=k)
    {
        po=pozi*2;
        if(po+1<=k&&d[heap[po]]>d[heap[po+1]])
            po++;
        if(d[heap[po]]<d[heap[pozi]])
        {
            swap(heap[po],heap[pozi]);
            swap(poz[heap[po]],poz[heap[pozi]]);
            pozi=po;
        }
        else
            break;
    }
}
void upDate(int pozi)
{
    while(pozi/2>0)
    {
        if(d[heap[pozi]]<d[heap[pozi/2]])
        {
            swap(heap[pozi],heap[pozi/2]);
            swap(poz[heap[pozi]],poz[heap[pozi/2]]);
            pozi/=2;
        }
        else
            break;
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    poz[++k]=heap[++k]=1;
    for(i=1;i<=n&&k>=1;i++)
    {
        if(k>=1)
        {
            viz[heap[1]]=1;
            node=heap[1];
            swap(heap[1],heap[k]);
            swap(poz[heap[1]],poz[heap[k]]);
            k--;
            downDate(1);
            for(j=0;j<G[node].size();j++)
            {
                nxt=G[node][j].first;
                cost=G[node][j].second;
                if(d[nxt]>d[node]+cost)
                {
                    d[nxt]=d[node]+cost;
                    if(viz[nxt]==1)
                        upDate(poz[nxt]);
                }
                if(viz[nxt]==0)
                {
                    viz[nxt]=1;
                    heap[++k]=nxt;
                    poz[nxt]=k;
                    upDate(k);
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]!=INF)
            fout<<d[i]<<" ";
        else
            fout<<0<<" ";
    return 0;
}