#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
struct Edge{
    std::size_t to;
    ll len;
    Edge(){}
    Edge(std::size_t a, ll b):to(a),len(b){}
};
bool operator<(const Edge &a, const Edge &b){
    return a.len>b.len;
}
std::vector<Edge> graph[1<<17];
std::size_t n;
const ll inf=100000000000000000L;
struct FixCmp{
    inline bool operator()(const Edge &a, const Edge &b) const{
        if(a.to!=b.to) return a.to!=b.to;
        return a.len<b.len;
    }
};
void fix(std::size_t i){
    if(graph[i].empty()) return;
    std::sort(graph[i].begin(), graph[i].end(), FixCmp());
    std::size_t k=1;
    for(std::size_t j=1;j<graph[i].size();++j){
        if(graph[i][j].to!=graph[i][j-1].to){
            graph[i][k++]=graph[i][j];
        }
    }
    graph[i].resize(k);
    return;
}
ll path[1<<17];
bool used[1<<17];
void dijkstra(){
    for(std::size_t i=0;i<n;i++){
        fix(i);
    }
    std::fill(path, path+n, inf);
    std::priority_queue<Edge> q;
    q.push(Edge(0, 0));
    path[0]=0;
    while(true){
        while(!q.empty() && (path[q.top().to]!=q.top().len || used[q.top().to])) q.pop();
        if(q.empty()) break;
        std::size_t v=q.top().to;
        used[v]=true;
        while(!q.empty() && (path[q.top().to]!=q.top().len || used[q.top().to])) q.pop();
        for(std::size_t i=0;i<graph[v].size();i++){
            Edge e=graph[v][i];
            if(path[v]+e.len<path[e.to]){
                path[e.to]=path[v]+e.len;
                q.push(Edge(e.to, path[e.to]));
            }
        }
    }
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::size_t m;
    std::cin>>n>>m;
    while(m--){
        std::size_t q, a, b;
        ll c;
        std::cin>>q>>a>>b>>c;
        a--;b--;
        if(q==1){
            graph[a].push_back(Edge(b, c));
        }else{
            for(std::size_t i=0;i<graph[a].size();i++){
                graph[b].push_back(Edge(graph[a][i].to, graph[a][i].len+c));
            }
            fix(b);
        }
    }
    dijkstra();
    for(std::size_t i=1;i<n;i++) std::cout<<(path[i]==inf?-1:path[i])<<'\n';
    return 0;
}
