#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#define INF 10000000000000000
using namespace std;
int n,m;
struct edge
{
    int to,wg;
};
long long dp[10000001];
vector <edge> a[1000001];
queue <int> next;
int dejecstra(int start)
{
    for(int i=1;i<=n;i++)dp[i]=INF;
  //  memset(used,0,sizeof(used));
   // used[start]=1;
    dp[start]=0;
    next.push(start);
    while(!next.empty())
    {
        int k=next.front();
        //used[k]=1;
        //cout<<k<<endl;
        next.pop();
        {
            for(int i=0;i<a[k].size();i++)
            {
                //cout<<used[a[k][i].to]<<endl;
                if(dp[k]+a[k][i].wg<dp[a[k][i].to])
                  {
                      next.push(a[k][i].to);
                      dp[a[k][i].to]=dp[k]+a[k][i].wg;
                  }
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int st,a1,b,c;
        scanf("%d%d%d%d",&st,&a1,&b,&c);
        if(st==1)
        {
            edge tt;
            tt.to=b;
            tt.wg=c;
            a[a1].push_back(tt);
        }
        else
        if(st==2)
        {
            for(int j=0;j<a[a1].size();j++)
            {
                edge tt;
                tt.to=a[a1][j].to;
                tt.wg=a[a1][j].wg+c;
                a[b].push_back(tt);
            }
        }
    }
    dejecstra(1);
    for(int i=2;i<=n;i++){
            if(dp[i]==INF)cout<<"-1"<<endl;else
            cout<<dp[i]<<endl;}
    return 0;
}
