#include <fstream>
#include<climits>
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
struct bla
{
    int nod,urm,cost;
} t[500010];
int n,m,w;
int start[50010];
int heap[500010];
int d[50010];
void read ()
{ int a,b,c,k=0;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        t[++k].nod=b; t[k].urm=start[a]; start[a]=k; t[k].cost=c;
    }
}
void climb (int poz)
{
    int key=heap[poz];
    while(3>2)
    {
        if(poz>1 && d[key]<d[heap[poz/2]])
            heap[poz]=heap[poz/2],poz/=2;
        else { heap[poz]=key; break; }
    }
}
void down (int poz)
{ int key=heap[poz];
    while(3>2)
    {
        int fiu=0;
        if(poz*2<=w) fiu=poz*2;
        if(poz*2+1<=w && d[heap[fiu+1]]<d[heap[fiu]]) fiu++;
        if(fiu && d[key]>d[heap[fiu]])
            heap[poz]=heap[fiu],poz=fiu;
            else { heap[poz]=key; break; }
    }
}
void dijkstra ()
{
    heap[++w]=1;
    while(w)
    {
        int varf=heap[1];
        for(int x=start[varf];x;x=t[x].urm)
            if(d[varf]+t[x].cost<d[t[x].nod])
            {
                d[t[x].nod]=d[varf]+t[x].cost;
                heap[++w]=t[x].nod;
                climb(w);
            }
            heap[1]=heap[w--];
            down(1);
    }
}
void init ()
{
    for(int i=2;i<=n;i++)
        d[i]=INT_MAX;
}
void write ()
{
    for(int i=2;i<=n;i++)
    {
        if(d[i]==INT_MAX) d[i]=0;
        cout<<d[i]<<" ";
    }
}
int main()
{
    read();
    init();
    dijkstra();
    write();
    cin.close();
    cout.close();
    return 0;
}