/**
  Spring training session
  Task 4: xair.cpp
  Vasil Yasenov Sarafov
**/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

struct my
{
    int y;
    long long t;
    my () {};
    my (int _y, long long _t)
    {
        y = _y;
        t = _t;
    }

}tmp;

const long long INF = 100000001;
const int NO_PARENT = -1;

bool v[1<<20];
int n, m, code;
int a, b;
long long graph[1<<12][1<<12];
long long d[1<<10];
long long c, dist;

void Dijkstra(int vertex);

int main(void)
{
    scanf("%i %i", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%i", &code);
        scanf("%i %i %lld", &a, &b, &c);

        if(code == 1)
        {
            graph[a][b] = c;
        }
        else if(code == 2)
        {
            for(int i = 1; i <= n; i++)
            {
                if(graph[a][i]) graph[b][i] = graph[a][i] + c;
            }
        }
    }

    //printGraph();
    Dijkstra(1);

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

void Dijkstra(int vertex)
{
    for(int i = 1; i <= n; i++)
    {
        if(!graph[vertex][i])
        {
            d[i] = INF;
        }
        else
        {
            d[i] = graph[vertex][i];
        }
    }
    memset(v, true, sizeof(v));
    v[vertex] = false;


    while(true)
    {
        int j = NO_PARENT, f = 0;
        long long di = INF;

        for(int i = 1; i <= n; i++)
        {
            if(v[i] && d[i] < di)
            {
                di = d[i];
                j = i;
            }
        }

        if (j == NO_PARENT) break;
        v[j] = false;

        for(int i = 1; i <= n; i++)
        {
            if(v[i] && graph[j][i] != 0)
            {
                if(d[i] > d[j] + graph[j][i])
                {
                    d[i] = d[j] + graph[j][i];
                }
            }
        }
    }
}

/**
4 3
1 1 2 10
2 1 3 -9
1 1 3 8
**/
