#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){}
};
std::vector<Edge> graph[100000];
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[100000];
std::size_t min[1<<18];
bool used[1<<17];
void set(std::size_t v){
    std::size_t i=(1<<16)+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(){
    for(std::size_t i=0;i<(1<<17);i++) min[(1<<17)+i]=i;
    for(std::size_t i=(1<<17)-1;i;i--) min[i]=min[i*2];
    for(std::size_t i=n;i<(1<<17);i++) used[i]=true;
    set(0);
    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;
}
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[a].push_back(Edge(b, c));
        }else{
            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;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::size_t m;
    std::cin>>n>>m;
    std::fill(path+1, path+n, inf);
    if(n<=2000){
        read1(m);
    }else{
        read2(m);
    }
    for(std::size_t i=0;i<n;i++) fix(i);
    dijkstra();
    for(std::size_t i=1;i<n;i++) std::cout<<(path[i]==inf?static_cast<ll>(-1):path[i])<<'\n';
    return 0;
}
