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

const int MAXN = 100003;
const int INF = 1 << 30;

int n;
vector<pair<int, int> > nb[MAXN];
int dist[MAXN];
bool used[MAXN];

void read() {
    int m;
    scanf("%d %d", &n, &m);

    int op, a, b, c;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d %d", &op, &a, &b, &c);
        if(op == 1) {
            nb[a].push_back(pair<int, int>(b, c));
        } else {
            for(vector<pair<int, int> >::iterator it = nb[a].begin(); it != nb[a].end(); it++) {
                nb[b].push_back(pair<int, int>((*it).first, (*it).second + c));
            }
        }
    }
}

void addNbs(int a) {
    if(!nb[a].empty()) {
        for(vector<pair<int, int> >::iterator it = nb[a].begin(); it != nb[a].end(); it++) {
            if((dist[(*it).first] == 0) || (dist[a] + (*it).second < dist[(*it).first])) {
                dist[(*it).first] = dist[a] + (*it).second;
            }
        }
    }
}

void printDist() {
    for(int i = 2; i <= n; i++) {
        printf("%d ", (dist[i]==0)?(-1):(dist[i]));
    }
    printf("\n");
}

int findMin() {
    int min = INF, minAt = -1;

    for(int i = 2; i <= n; i++) {
        if(dist[i]!=0 && !used[i] && dist[i]<min) {
            min = dist[i];
            minAt = i;
        }
    }
    //cout << "minAt: " << minAt << endl;
    //printDist();
    return minAt;
}

void dk() {
    addNbs(1);
    used[1] = true;

    int currMin;
    while(true) {
        currMin = findMin();
        if(currMin == -1) {
            return;
        }
        used[currMin] = true;
        addNbs(currMin);
    }
}

void solve() {
    dk();
    for(int i = 2; i <= n; i++) {
        printf("%d\n", (dist[i]==0)?(-1):(dist[i]));
    }
}

int main() {
    read();
    solve();
    return 0;
}
