#include<iostream>
using namespace std;

int n,m,eind;
struct rebro{int x,y,w; }e[100001];

bool used[4005];
int dist[4005];
void dijkstra(int node)
{
   int i,mind=0;

   for(i=1;i<=n;i++)
      dist[i]=1000000000;
   dist[node]=0;

   while(mind!=1000000000)
   {
      for(i=0;i<eind;i++)
         if(e[i].x==node && !used[e[i].y])
            dist[i]=min(dist[i],dist[node]+e[i].w);
      used[node]=true;

      mind=1000000000;
      for(i=1;i<=n;i++)
         if(!used[i] && dist[i]<mind)
         {
            mind=dist[i];
            node=i;
         }
   }
}

int main()
{
   int i,j,type,a,b,c;
   bool found;

   cin>>n>>m;

   for(i=0;i<m;i++)
   {
      cin>>type>>a>>b>>c;

      found=false;

      if(type==1)
         for(i=0;i<eind;i++)
            if( a==e[i].x && b==e[i].y )
            {
               e[i].w=min(e[i].w,c);
               found=true;
               break;
            }

      if(found==false)
      {
         e[eind].x=a;
         e[eind].y=b;
         e[eind].w=c;
         eind++;
      }

      /*if(type==2)
         for(j=1;j<=n;j++)
            if(w[a][j])
               if(w[b][j]==0 || w[b][j]>w[a][j]+c)
                  w[b][j]=w[a][j]+c;*/
   }

   /*for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
         if(w[i][j]!=0)
            cout<<i<<' '<<j<<' '<<w[i][j]<<endl;*/

   dijkstra(1);

   for(i=2;i<=n;i++)
      if(dist[i]==1000000000) cout<<-1<<endl;
      else  cout<<dist[i]<<endl;

   return 0;
}

/*
4 3
1 1 2 10
2 1 3 -9
1 1 3 8
*/
