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

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()
{
scanf("%ld%ld",&n,&m);
long i,a,b,c;
init();
for (i=1;i<=m;i++)
    {
     scanf("%ld%ld%ld",&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]);
       }
    }
}

long search(long a,long b)
{
nod *p;
for (p=t[a];p!=NULL;p=p->urm)
    {
     if (p->n==b)
        {
         return p->c;
        }
    }
return inf;
}

void dijkstra()
{
long i,p;
long 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 (i=2;i<=n;i++)
           {
            k=search(p,i);
            if (d[i]>d[p]+k)
                d[i]=d[p]+k;
            if (poz[i]/2)
                if (d[h[poz[i]/2]]>d[i])
                    percolate(poz[i]);
                else sift(poz[i]);
            else sift(poz[i]);
           }
      }
}

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

int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
read();
dijkstra();
print();
return 0;
}