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

const int INF = 999999999;
int code;
int a, b, n, m;
int G[1<<10][1<<10];
long long c;

void FloydAlgorithm(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)
        {
            G[a][b] = c;
        }
        else if(code == 2)
        {
            for(int i = 1; i <= n; i++)
            {
                if(G[a][i]) G[b][i] = G[a][i] + c;
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(!G[i][j]) G[i][j] = INF;
        }
    }
    FloydAlgorithm(1);
    for(int i = 2; i <= n; i++)
    {
        if(G[1][i] == INF) printf("%i\n", -1);
        else printf("%i\n", G[1][i]);
    }
    return 0;
}

void FloydAlgorithm(int vertex)
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(G[i][j] > (G[i][k] + G[k][j]))
                {
                    G[i][j] = G[i][k] + G[k][j];
                }
            }
        }
    }
}
/**
4 3
1 1 2 10
2 1 3 -9
1 1 3 8
**/
