#include<fstream>
#define nmax 50005
#define inf 52000000
long n,m,h[nmax],poz[nmax];
long d[nmax];

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod
{
nod *urm;
int n,c;
};

nod *t[nmax];

void InsertBegin(long a,long b,long c)
{
nod *aux;
aux=new nod;
aux->n=b;
aux->c=c;
aux->urm=t[a];
t[a]=aux;
}

void percolate(long k)
{
long aux;
while (d[h[k]]<d[h[k/2]] && k/2)
      {
       aux=poz[h[k]];
       poz[h[k]]=poz[h[k/2]];
       poz[h[k/2]]=aux;
       aux=h[k];
       h[k]=h[k/2];
       h[k/2]=aux;
       k=k/2;
      }
}

void sift(long k)
{
long f,aux,p;
do
{
f=0;
if (2*k<h[0])
   {
    if (d[h[2*k]]<d[h[k]])
       {
        p=2*k;
        f=1;
       }
   if (2*k+1<h[0])
      if (d[h[2*k+1]]<d[h[k]])
         {f=1;
          if (d[h[2*k+1]]<d[h[2*k]])
              p=2*k+1;
         }
   }
if (f)
   {
    aux=poz[h[p]];
    poz[h[p]]=poz[h[k]];
    poz[h[k]]=aux;
    aux=h[k];
    h[k]=h[p];
    h[p]=aux;
    k=p;
   }
}
while (f);
}

void init()
{
long i;
h[0]=n-1;
for (i=2;i<=n;i++)
    {
     d[i]=inf;
     poz[i]=i-1;
     h[i-1]=i;
    }
}

void read()
{
f>>n>>m;
long i,a,b,c;
init();
for (i=1;i<=m;i++)
    {
     f>>a>>b>>c;
     InsertBegin(a,b,c);
     if (a==1)
        {
         d[b]=c;
         if (poz[b]/2)
             if (d[h[poz[b]/2]]>d[b])
                 percolate(poz[b]);
             else sift(poz[b]);
         else sift(poz[b]);
       }
    }
}

void dijkstra()
{
long i,p;
nod *k;
while (h[0])
      {
       p=h[1];
       poz[h[1]]=-1;
       h[1]=h[h[0]];
       poz[h[h[0]]]=1;
       h[0]--;
       sift(1);
       for (k=t[p];k!=NULL;k=k->urm)
           {
            if (d[k->n]>d[p]+k->c)
               {
                d[k->n]=d[p]+k->c;
                if (poz[k->n]/2)
                    if (d[h[poz[k->n]/2]]>d[k->n])
                        percolate(poz[k->n]);
                    else sift(poz[k->n]);
                else sift(poz[k->n]);
               }
           }
     }
}

void print()
{
long i;
for (i=2;i<=n;i++)
    if (d[i]==inf)
        g<<"0 ";
    else g<<d[i]<<" ";
}

int main()
{
read();
dijkstra();
print();
return 0;
}