#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1 << 19;

struct vertex{;
    int v;
    long long dist;

    vertex(){};
    vertex ( int _v, int _dist ){
        v = _v;
        dist = _dist;
    }

    bool operator< ( vertex t1 )const {
        return dist > t1.dist;
    };
};
struct oper{
    int type, A, B, C;
};

struct edge{
    int to, dist, ff;

    edge(){}
    edge ( int _to, int _dist ){
        to = _to;
        dist = _dist;
        ff = 0;
    }
    edge ( int _to, int _dist, int _ff ){
        to = _to;
        dist = _dist;
        ff = _ff;
    }
};

int neg[MAXN];
oper o[1 << 17];
vector < edge > v[MAXN];
vector < int > vv[1 << 17];
int sz;
int N, M, pos[1 << 17];
priority_queue <vertex> q;
int used[MAXN];
long long dist[MAXN];
int MX[MAXN];

void scan(){
    scanf ( "%d%d", &N, &M );

    for ( int i = 0; i < M; ++i )
        scanf ( "%d%d%d%d", &o[i].type, &o[i].A, &o[i].B, &o[i].C );
}

void fillVV(){
    sz = N + 1;

    for ( int i = 0; i < M; ++i )
        if ( o[i].type == 1 ) vv[o[i].A].push_back ( sz++ );
        else
            vv[ o[i].B ].push_back ( sz++ );
}

void fillV(){
    memset ( pos, -1, sizeof ( pos ) );

    for ( int i = 0; i < M; ++i )
        if ( o[i].type == 1 ){
            ++pos[o[i].A];
            v[ vv[o[i].A][pos[o[i].A] ] ].push_back ( edge ( o[i].B, o[i].C ) );
        }
        else{
            ++pos[o[i].B];
            if ( pos[ o[i].A ] != -1 )
                v[ vv[o[i].B][pos[o[i].B] ] ].push_back ( edge ( vv[ o[i].A ][pos[o[i].A]], o[i].C ) );

        }

    for ( int i = 1; i <= N; ++i ){

        for ( int j = 1; j < vv[i].size(); ++j ){
            v[ vv[i][j] ].push_back ( edge ( vv[i][j - 1], 0 ) );
        }
        if ( vv[i].size() ) v[i].push_back ( edge ( vv[i].back(), 0 ) );
    }
}

void dijkstra ( int start ){
    for ( int i = 0; i < MAXN; ++i )
        dist[i] = 1e16;
    dist[start] = 0;

    q.push ( vertex ( start, dist[start] ) );

    while ( !q.empty() ){
        int i = q.top().v;

        if ( used[i] )
            q.pop();
        used[i] = 1;
        for ( int j = 0; j < v[i].size(); ++j ){
            if ( !used[ v[i][j].to ] && dist[ v[i][j].to ] > dist[i] + v[i][j].dist ){
                dist[ v[i][j].to ] = dist[i] + v[i][j].dist;
                q.push ( vertex ( v[i][j].to, dist[ v[i][j].to ] ) );
            }
        }

    }

}
void solve(){
    fillVV();
    fillV();

    dijkstra(1);

   /*for ( int i = 1; i <= N; ++i ){
        cout << i << ":";

        for ( int j = 0; j < vv[i].size(); ++j )
            cout << vv[i][j] << " ";
        cout << endl;
        }
    for ( int i = 1; i <= sz; ++i ){
        cout << i << ":";

        for ( int j = 0; j < v[i].size(); ++j )
            cout << v[i][j].to << "," << v[i][j].dist << "  ";
        cout << endl;
    }*/

    if ( N * M < 1e7 ){
        int ok = 1;
        while ( ok ){
            ok = 0;
            for ( int i = 1; i < sz; ++i )
                for ( int j = 0; j < v[i].size(); ++j )
                    if ( dist[i] + v[i][j].dist < dist[ v[i][j].to] ){
                        dist[ v[i][j].to ] = dist[i] + v[i][j].dist;
                        ok = 1;
                    }
        }
    }
    for ( int i = 0; i < MAXN; ++i )
        if ( dist[i] == 1e16 )
            dist[i] = -1;
    for ( int i = 2; i <= N; ++i )
        printf ( "%lld\n", dist[i] );
}

int main(){
    scan();
    solve();
}
