#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>

#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;

typedef pair<LL, LL> PLL;

const int MAXN = 100100;
const int MAXM = 100100;
const LL INF = 1LL << 60;

int n, m;
short int cmd[MAXM];
LL a[MAXM], b[MAXM], c[MAXM];
vector< PLL > g[MAXN];
bool used[MAXN];
LL d[MAXN];
bool subTaskTwo = true;
priority_queue< PLL > pq;
int Acmd2idx[MAXN];
vector< PLL > Bcmd2[MAXN];

void read() {
    memset(Acmd2idx, -1, sizeof(Acmd2idx));

    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i ++) {
        scanf("%d %lld %lld %lld", &cmd[i], &a[i], &b[i], &c[i]);
        if(cmd[i] == 2) {
            Acmd2idx[ a[i] ] = i;
            Bcmd2[ b[i] ].pb(mp(a[i], c[i]));
            subTaskTwo = false;
        }
    }
}

void initOne() {
    static LL ma3x[2010][2010];

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            ma3x[i][j] = INF;

    for(int i = 0; i < m; i ++)
        if(cmd[i] == 1) ma3x[ a[i] ][ b[i] ] = min(ma3x[ a[i] ][ b[i] ], c[i]);
        else {
            for(int j = 1; j <= n; j ++)
                if(ma3x[ a[i] ][ j ] != INF)
                    ma3x[ b[i] ][ j ] = min(ma3x[ b[i] ][ j ], ma3x[ a[i] ][ j ] + c[i]);
        }

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(ma3x[i][j] != INF)
                g[i].pb(mp(j, ma3x[i][j]));
}

void init() {
    for(int i = 0; i < m; i ++)
        if(cmd[i] == 1)
            g[ a[i] ].pb(mp(b[i], c[i]));
}

void dijkstraOneAndTwo() {
    for(int i = 1; i <= n; i ++)
        d[i] = INF;

    pq.push(mp(0, 1));
    while(!pq.empty()) {
        PLL tmp = pq.top();
        pq.pop();

        tmp.first *= (-1);

        if(used[tmp.second]) continue;
        used[tmp.second] = true;
        d[tmp.second] = tmp.first;

        for(int i = 0; i < g[tmp.second].size(); i ++) {
            LL nextNode = g[tmp.second][i].first;
            LL cost = tmp.first + g[tmp.second][i].second;
            if(!used[nextNode] && d[nextNode] > cost) {
                d[nextNode] = cost;
                pq.push(mp(-cost, nextNode));
            }
        }
    }

    for(int i = 2; i <= n; i ++)
        if(d[i] == INF) printf("-1\n");
        else printf("%lld\n", d[i]);
}

void dijkstraThree() {
    for(int i = 1; i <= n; i ++)
        d[i] = INF;

    pq.push(mp(0, 1));
    while(!pq.empty()) {
        PLL tmp = pq.top();
        pq.pop();

        tmp.first *= (-1);

        if(used[tmp.second]) continue;

        used[tmp.second] = true;
        d[tmp.second] = tmp.first;

        LL vertexCost = tmp.first;
        if(Acmd2idx[tmp.second] != -1) vertexCost = min(vertexCost, d[ b[ Acmd2idx[tmp.second] ] ] + c[ Acmd2idx[tmp.second] ]);

        for(int i = 0; i < g[tmp.second].size(); i ++) {
            LL nextNode = g[tmp.second][i].first;
            LL cost = vertexCost + g[tmp.second][i].second;
            if(!used[nextNode] && d[nextNode] > cost) {
                d[nextNode] = cost;
                pq.push(mp(-cost, nextNode));
            }
        }

        for(int i = 0; i < Bcmd2[tmp.second].size(); i ++) {
            int curA = Bcmd2[tmp.second][i].first;
            if(d[curA] > d[tmp.second] + Bcmd2[tmp.second][i].second) {
                vertexCost = d[tmp.second] + Bcmd2[tmp.second][i].second;
                for(int j = 0; j < g[curA].size(); j ++) {
                    LL nextNode = g[curA][j].first;
                    LL cost = vertexCost + g[curA][j].second;
                    if(!used[nextNode] && d[nextNode] > cost) {
                        d[nextNode] = cost;
                        pq.push(mp(-cost, nextNode));
                    }
                }
            }
        }
    }

    for(int i = 2; i <= n; i ++)
        if(d[i] == INF) printf("-1\n");
        else printf("%lld\n", d[i]);
}

int main()
{
    read();

    if(n <= 2000 && m <= 4000) {
        initOne();
        dijkstraOneAndTwo();
        return 0;
    }

    if(subTaskTwo) {
        init();
        dijkstraOneAndTwo();
        return 0;
    }

    init();
    dijkstraThree();

    return 0;
}
