#include<iostream>
using namespace std;

int n,m;
int w[4005][4005];

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=1;i<=n;i++)
         if(w[node][i])
            dist[i]=min(dist[i],dist[node]+w[node][i]);
      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;

   cin>>n>>m;

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

      if(type==1)
         if(w[a][b]==0 || w[a][b]>c)
            w[a][b]=c;

      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
*/
