/**
  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<<10];
int n, m, code;
int a, b;
long long d[1<<10];
long long c, dist;
vector <my> graph[1<<10];

void Dijkstra(int vertex);
void printGraph();

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)
        {
            tmp = my(b, c);
            graph[a].push_back(tmp);
        }
        else if(code == 2)
        {
            for(int j = 0; j < graph[a].size(); j++)
            {
                dist = graph[a][j].t + c;
                tmp = my(graph[a][j].y, dist);
                graph[b].push_back(tmp);
            }
        }
    }
    //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 = 0; i < graph[vertex].size(); i++)
    {
        d[graph[vertex][i].y] = graph[vertex][i].t;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!d[i])
        {
            d[i] = INF;
        }

    }

    for(int i = 1; i <= n; i++) v[i] = true;

    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++)
        {
            bool broken = false;
            if(v[i])
            {
                for(int pos = 0; pos < graph[j].size(); pos++)
                {
                    if(graph[j][pos].y == i)
                    {
                        f = pos;
                        broken = true;
                        break;
                    }
                }
                if(broken) if(d[i] > (d[j] + graph[j][f].t))
                {
                    d[i] = d[j] + graph[j][f].t;
                }
            }
        }
    }
}

void printGraph()
{
    for(int i = 1; i <= n; i++)
    {
        printf("%i -", i);
        for(int j = 0; j < graph[i].size(); j++)
        {
            printf("%i %i, ", graph[i][j].y, graph[i][j].t);
        }
        printf("\n");
    }
}
/**
4 3
1 1 2 10
2 1 3 -9
1 1 3 8
**/
