#include <iostream>
#include <queue>
#include <cstdio>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;

typedef long long ll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int n, m;
const int maxn = 100005;
const ll INF = 100000000000000ll;

bool used[maxn];
ll d[maxn];
vector<pil> g[maxn];

struct vert {
            int u;
            vert() {};
            vert(int _u) : u(_u) {};
            bool operator < (const vert & r) const { return d[u] > d[r.u]; }
            };
priority_queue < vert > q;

void dijkstra(int u) {
    int i;

    for(i=2; i<=n; i++) d[i] = INF;
    q.push( vert(u) );

    vert t;
    int v, w, cur;

    while(!q.empty()) {
        t = q.top(); q.pop();
        v = t.u;
        if(used[v]) continue;
        used[v] = 1;

        for(i=0; i<g[v].size(); i++)
        {
        u = g[v][i].f, w = g[v][i].s;
        if(u == v) continue;
        cur = d[v] + w;
        if(!used[u] && d[u] > cur)
                d[u] = cur,
                q.push ( vert(u) );
        }
     }
}

int main() {
    int cmd, a, b;

    scanf("%d%d", &n, &m);

    int i;
    ll c;
    while(m--) {
        scanf("%d%d%d%lld", &cmd, &a, &b, &c);
        if(cmd == 1) g[a].pb( mp(b, c) );
        else
            for(i=0; i<g[a].size(); i++)
                g[b].pb( mp(g[a][i].f, g[a][i].s + c ) );
        }

    dijkstra(1);
    for(i=2; i<=n; i++) printf("%lld\n", (d[i] == INF) ? -1 : d[i]);
    return 0;
    }
