#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int INF = 999999999;

struct path
{
    int i,j,h;
};

vector<path> q;

void New(int a,int b,int c)
{
    path e;
    e.i=a-1;
    e.j=b-1;
    e.h=c;
    q.push_back(e);
}

void Add(int a,int b,int c)
{
    path e;
    e.i=b-1;
    for(int i=0;i<q.size();i++)
    {
        if(q[i].i==a-1)
        {
            e.j=q[i].j;
            e.h=q[i].h+c;
            q.push_back(e);
        }
    }
}
int n,m;
vector< vector<int> > Matrx;

void makeMatrx()
{
    vector<int> zero(n,0);
    for(int i=0;i<n;i++)Matrx.push_back(zero);

    for(int i=0;i<q.size();i++)
    {
        if(Matrx[q[i].i][q[i].j]==0 || Matrx[q[i].i][q[i].j]>=q[i].h) Matrx[q[i].i][q[i].j]=q[i].h;
    }
}

vector<int> d;

void dij(int s)
{
    for(int i=0;i<n;i++)
    {
        if(Matrx[s][i]==0)d.push_back(INF);
        else d.push_back(Matrx[s][i]);
    }

    bool T[n+1];

    for(int i=0;i<n;i++)T[i]=1;
    T[s]=0;

    while(true)
    {
        int j=-1;
        int sj=INF;
        for(int i=0;i<n;i++)
        {
            if(sj>d[i] && T[i]){sj=d[i];j=i;}
        }

        if(j==-1)break;
        T[j]=0;

        for(int i=0;i<n;i++)
        {
            if(Matrx[j][i])
            {
                if(d[j]+Matrx[j][i]<d[i])d[i]=d[j]+Matrx[j][i];
            }
        }

    }
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int type,a,b,c;
        scanf("%d%d%d%d",&type,&a,&b,&c);
        if(type==1)New(a,b,c);
        else Add(a,b,c);
    }
    makeMatrx();
    dij(0);
    for(int i=1;i<n;i++)if(d[i]==INF)cout<<-1<<endl;else cout<<d[i]<<endl;
    return 0;
}
