#include <fstream>
#include <vector>
#define s 1
using namespace std;
vector<int>w[50003];
vector<int>v[50003];
int d[50001],poz[50001],heap[50001],h,n,m,u,S[50001];
int father(int i)
{
    return (i/2);
}
int left(int i)
{
    return(i*2);
}
int right(int i)
{
    return (i*2+1);
}
void coboara(int i)
{
    int minim;
    minim=i;
    if(left(i)<=h and d[heap[i]]>d[heap[left(i)]]) minim=left(i);
    if(right(i)<=h and d[heap[minim]]>d[heap[right(i)]]) minim=right(i);
    if(minim!=i)
    {
        swap(poz[heap[i]],poz[heap[minim]]);
        swap(heap[i],heap[minim]);
        coboara(minim);
    }
}
void urca(int i)
{
    int key=heap[i];
    while(i>1 and d[key]<d[heap[father(i)]])
    {
        heap[i]=heap[father(i)];
        poz[heap[father(i)]]=i;
        i=father(i);
    }
    heap[i]=key;
    poz[key]=i;
}
int extract()
{
    swap(heap[1],heap[h]);
    swap(poz[heap[1]],poz[heap[h]]);
    h--;
    coboara(1);
    return heap[h+1];
}
void init()
{
    int i;
    for(i=1;i<=n;i++)
    {
        d[i]=int(2e9);
        heap[i]=i;
    }
    d[s]=0;
    h=n;
}

void dijkstra()
{
    int i,x;
    while(h!=0)
    {
        u=extract();
        S[++S[0]]=u;
        x=v[u].size();
        for(i=0;i<x;i++)
        if(d[v[u][i]]>d[u]+w[u][i]){
                                    d[v[u][i]]=d[u]+w[u][i];
                                    urca(poz[v[u][i]]);
                                   }

    }
}
int main()
{
    int i,x,y,c;
    ifstream fi("dijkstra.in");
    ofstream fo("dijkstra.out");
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
        fi>>x>>y>>c;
        v[x].push_back(y);
        w[x].push_back(c);
    }
    init();
    dijkstra();
    for(i=2;i<=n;i++) fo<<d[i]<<" ";
    return 0;
}