#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
typedef long long Int;

struct gr
{
    Int ver,val;

    bool operator<( const gr& other ) const
    {
        return val>other.val;
    }
};

vector<gr> Graph[100001];
Int Distances[100001];
bool TFO[100001];
priority_queue<gr> myheap;
Int n,m;

void Djikstra()
{
    gr help;
    Int i,j;
    gr mytop;

    for (i=0;i<=100001;i++)
    {
        Distances[i]=-1;
        TFO[i]=false;
    }

    help.ver=1;
    help.val=0;
    myheap.push(help);

    for (i=1;i<=n;i++)
    {
        if (myheap.empty())
        {
            break;
        }
        mytop=myheap.top();

        while(TFO[mytop.ver] && !myheap.empty())
        {
            myheap.pop();
            mytop=myheap.top();
        }

        if (myheap.empty() && TFO[mytop.ver])
        {
            break;
        }

        TFO[mytop.ver]=true;
        Distances[mytop.ver]=mytop.val;

        for (j=0;j<Graph[mytop.ver].size();j++)
        {
            help.ver=Graph[mytop.ver][j].ver;
            help.val=mytop.val+Graph[mytop.ver][j].val;

            myheap.push(help);
        }
    }

    return;
}

int main()
{
    Int a,b,c;
    Int i,j;
    Int com;
    gr help;

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

    for (i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld %lld",&com,&a,&b,&c);

        if (com==1)
        {
            help.ver=b;
            help.val=c;
            Graph[a].push_back(help);
        }
        else
        {
            for (j=0;j<Graph[a].size();j++)
            {
                help.ver=Graph[a][j].ver;
                help.val=Graph[a][j].val+c;

                Graph[b].push_back(help);
            }
        }
    }

    Djikstra();

    for (i=2;i<=n;i++)
    {
        printf("%lld\n",Distances[i]);
    }

    return 0;
}
