#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], bat[MAXN];
int prev[MAXN], next[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 ) );
                if ( o[i].C < 0 )
                    ++neg[ vv[ o[i].A ][pos[o[i].A]] ];
            }

        }

    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 ) );
            prev[ vv[i][j - 1] ] = vv[i][j];
            next[ vv[i][j] ] = vv[i][j - 1];
        }
        if ( vv[i].size() ){
            prev[ vv[i].back() ] = i;
            next[i] = vv[i].back();
             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] ) );
    used[0] = 1;
    while ( !q.empty() ){
        int i = q.top().v;
        q.pop();
        if ( used[i] )
            continue;
        used[i] = 1;
        if (!neg[ next[i] ] )
            q.push ( vertex ( next[i], dist[ next[i] ] ) );
        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;
    }*/

        int ok = 1;
        for ( int i = 0; i < MAXN; ++i )
            bat[i] = 1;
        int br = 1;
        while ( ok ){
            ok = 0;
            ++br;
            for ( int i = 1; i < sz; ++i ) if ( dist[i] != 1e16 && bat[i] >= br - 1)
                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;
                        bat[v[i][j].to] = br;
                    }
        }

    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();
}

