#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define mp make_pair
#define pb push_back
using namespace std;
vector<pair <int, int> > v[1<<17];
int n, m, dist[1<<17];
bool used[1<<17];
void dijk(){
    priority_queue< pair<int, int> > q;
    q.push(mp(0,1));
    while(!q.empty()){
        int x = q.top().second;//, val = -q.top().first;
        q.pop();
        if(used[x]) continue;
        used[x] = true;
        for(int i = 0; i < v[x].size(); i++){
            int y = v[x][i].first, val = v[x][i].second;
            if(!used[y])
                if(dist[y] == -1 || dist[y] > val + dist[x]){
                    dist[y] = val + dist[x];
                    q.push(mp(-dist[y], y));
                }
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(; m > 0; m --){
        int op, A, B, C;
        scanf("%d%d%d%d", &op, &A, &B, &C);
        if(op==1)
            v[A].pb(mp(B,C));
        else
            for(int i = 0; i < v[A].size(); i++)
                v[B].pb(mp(v[A][i].first, v[A][i].second + C));
    }
    for(int i = 2; i <=n; i++)
        dist[i] = -1;
    dijk();
    for(int i = 2; i <= n; i++)
        printf("%d\n", dist[i]);
    return 0;
}
