#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
struct Edge{
    std::size_t to;
    ll len;
    bool real;
    Edge(){}
    Edge(std::size_t a, ll b, bool r=false):to(a),len(b),real(r){}
};
std::vector<Edge> graph[1<<18];
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][k-1].to){
            graph[i][k++]=graph[i][j];
        }
    }
    graph[i].resize(k);
    return;
}
ll path[1<<18];
std::size_t min[1<<19];
bool used[1<<18];
void set(std::size_t v){
    std::size_t i=(1<<17)+v/2;
    while(i!=0){
        if( !used[min[2*i+1]] && (path[min[2*i+1]]<path[min[2*i]]||used[min[2*i]]) ) min[i]=min[2*i+1];
        else min[i]=min[2*i];
        i>>=1;
    }
    return;
}
void dijkstra(std::size_t me){
    for(std::size_t i=0;i<(1<<18);i++) min[(1<<18)+i]=i;
    for(std::size_t i=(1<<18)-1;i;i--) min[i]=min[i*2];
    std::fill(used+n, used+(1<<18), true);
    path[me]=0;
    set(me);
    while(!used[min[1]]){
        std::size_t v=min[1];
        used[v]=true;
        set(v);
        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;
                set(e.to);
            }
        }
    }
    return;
}
void read1(std::size_t 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{
            fix(a);
            graph[b].reserve(graph[a].size()+graph[b].size());
            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));
            }
        }
    }
    return;
}
std::size_t mapped[1<<17];
void read2(std::size_t m){
    while(m--){
        std::size_t q, a, b;
        ll c;
        std::cin>>q>>a>>b>>c;
        a--;b--;
        if(q==1){
            graph[mapped[a]].push_back(Edge(b, c));
        }else{
            graph[mapped[b]].push_back(Edge(mapped[a], c, true));
            std::size_t oa=mapped[a];
            mapped[a]=n++;
            graph[mapped[a]].push_back(Edge(oa, 0, true));
        }
    }
    for(std::size_t i=0;i<n;i++){
        for(std::size_t j=0;j<graph[i].size();j++){
            if(!graph[i][j].real) graph[i][j].to=mapped[graph[i][j].to];
        }
    }
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::size_t m;
    std::cin>>n>>m;
    std::size_t n1=n;
    for(std::size_t i=0;i<n;i++){
        mapped[i]=i;
    }
    if(n<=2000){
        read1(m);
        for(std::size_t i=0;i<n;i++) fix(i);
    }else{
        read2(m);
    }
    std::fill(path, path+n, inf);
    dijkstra(mapped[0]);
    for(std::size_t i=1;i<n1;i++) std::cout<<(path[mapped[i]]==inf?static_cast<ll>(-1):path[mapped[i]])<<'\n';
    return 0;
}
