#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <utility>

typedef std::pair<int, int> pii;
int n, m;
struct rec {
    int node;
    int path;
    rec(){}
    rec(int n, int p) {
        node = n;
        path = p;
    }
};
std::vector<rec> neig[100001];

bool operator<(const rec &a, const rec &b) {
    return a.path > b.path;
}

std::map<int, int> dist;
std::priority_queue<rec> que;
void dijkstra(int start, bool add = false, int b = 0, int c = 0) {
    dist.clear();
    dist.insert(std::pair<int,int>(start,0));
    que.push(rec(start, 0));
    rec top;
    while (!que.empty()) {
        top = que.top(); que.pop();
        if (top.path > dist[top.node]) continue;
        for (size_t i = 0; i < neig[top.node].size(); ++i) {
            if (dist.find(neig[top.node][i].node) == dist.end()) {
                dist.insert(pii(neig[top.node][i].node, top.path + neig[top.node][i].path));
                que.push(rec(neig[top.node][i].node, top.path + neig[top.node][i].path));
            } else {
                if (dist[neig[top.node][i].node] > top.path + neig[top.node][i].path) {
                    dist[neig[top.node][i].node] = top.path + neig[top.node][i].path;
                    que.push(rec(neig[top.node][i].node, top.path + neig[top.node][i].path));
                }
            }
        }
    }
    if (add) {
        for (int i = 2; i < n; ++i) {
            if (dist.find(i) != dist.end()) {
                neig[b].push_back(rec(i, dist[i] + c));
            }
        }
    }
}

int main() {
    std::cin >> n >> m;
    for (int i = 0;i < m; ++i) {
        int code, a, b, c;
        std::cin >> code >> a >> b >> c;
        if (code == 1) {
            neig[a].push_back(rec(b,c));
        }
        if (code == 2) {
            dijkstra(a, true, b, c);
        }
    }
    dijkstra(1);
    for (int i = 2; i <= n; ++i) {
        if (dist.find(i) != dist.end()) {
            std::cout << dist[i] << '\n';
        } else {
            std::cout << "-1\n";
        }
    }
    return 0;
}
