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

#define mp make_pair
#define pb push_back

using namespace std;

typedef pair<int, int> PII;

const int MAXN = 100100;
const int MAXM = 100100;
const int INF = 1 << 30;

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

void read() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i ++) {
        scanf("%d %d %d %d", &cmd[i], &a[i], &b[i], &c[i]);
        if(cmd[i] == 2) subTaskTwo = false;
    }
}

void initOne() {
    static int 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 initTwo() {
    for(int i = 0; i < m; i ++)
        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()) {
        PII 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 ++) {
            int nextNode = g[tmp.second][i].first;
            int 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("%d\n", d[i]);
}

int main()
{
    read();

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

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

    return 0;
}
