#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct rebro{
    int to;
    int len;
};
struct vruh{
    int ind;
    int st;
};
struct cmp{
    bool operator()(const vruh a,const vruh b)const{
        return a.st>b.st;
    }
};
vector<rebro> reb[100200];
priority_queue<vruh,vector<vruh>,cmp> v;
int n,m,o,k,l,p,br;
int vurhove[100200];
bool used[100200];
rebro r;
vruh vr;
void dijkstra(){
    vr.ind=1;
    vr.st=0;
    vurhove[1]=0;
    v.push(vr);
    int tek;
    while (!v.empty()){
        tek=v.top().ind;
        v.pop();
        if (used[tek]==0){
            used[tek]=1;
            for (int i=0;i<reb[tek].size();++i){
                if (vurhove[reb[tek][i].to]==-1||
                    vurhove[reb[tek][i].to]>vurhove[tek]+reb[tek][i].len){
                    vr.ind=reb[tek][i].to;
                    vr.st=vurhove[tek]+reb[tek][i].len;
                    vurhove[vr.ind]=vr.st;
                    v.push(vr);
                }
            }
        }
    }
    return;
}
int main(){
    scanf("%d%d",&m,&n);
    for (int i=0;i<=m;++i){vurhove[i]=-1;}
    for (int i=0;i<n;++i){
        scanf("%d%d%d%d",&o,&k,&l,&p);
        if (o==1){
            r.len=p;r.to=l;
            reb[k].push_back(r);
        }else{
            for (int j=0;j<reb[k].size();++j){
                r.to=reb[k][j].to;
                r.len=p+reb[k][j].len;
                reb[l].push_back(r);
            }
        }
    }
    dijkstra();
    for (int i=2;i<=m;++i){printf("%d\n",vurhove[i]);}
    return 0;
}
