#include <fstream>
#define inf 50000001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct node
{
    int nr,dist;
    node *next;
} *v[50001];

int d[50010],h[50010],n,m,poz[50010],nr;

void build_graph ()
{
    int a,b,di;
    node *d;
    fin>>a>>b>>di;
    d=new node;
    d->nr=b;
    d->dist=di;
    d->next=v[a];
    v[a]=d;
}

void upheap (int i)
{
    int x=h[i];
    int j=i/2;
    while (d[x] < d[h[j]])
    {
        h[i]=h[j];
        poz[h[i]]=i;
        i=j;
        j=j/2;
    }
    h[i]=x;
    poz[h[i]]=i;
}

void downheap (int i)
{
    int j;
    int x=h[i];
    do
    {
      j=-1;
      if (i*2<=n && d[h[i*2]]<d[x]) j=i*2;
      if (i*2+1<=n && d[h[i*2+1]]<d[x]) { if(j==i*2) {if (d[h[i*2+1]]<d[h[j]]) j=i*2+1;}
                                        else j=i*2+1;}
      if (j!=-1)
      {
          h[i]=h[j];
          poz[h[i]]=i;
          i=j;
      }
    }while (j!=-1);
    h[i]=x;
    poz[h[i]]=i;
}

void dijkstra ()
{
    int x;
    for (int i=1;i<=n;i++) d[i]=inf;

    d[n+1]=inf;

    d[1]=0;

    for (int i=1;i<=n;i++) {h[i]=i; poz[i]=i;}

    while (d[h[1]]!=inf)
    {
        x=h[1];
        node *p=v[x];
        while (p)
        {
            if (d[x]+p->dist<d[p->nr])
            {
                d[p->nr]=d[x]+p->dist;
                upheap(poz[p->nr]);
            }
            p=p->next;
        }
        h[1]=n+1;
        downheap (1);
    }

}

int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;i++) build_graph ();
    dijkstra ();
    for (i=2;i<=n;i++) if (d[i]==inf) d[i]=0;
    for (i=2;i<=n;i++) fout<<d[i]<<" ";
}