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

struct gr
{
    Int ver,val;
};

vector<gr> Graph[100001];
Int n,m;
bool TFO[100001];
Int Dist[100001];
vector<gr> myheapy;

bool AwesomeCompare(gr a,gr b)
{
    return a.val>b.val;
}

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

    for (i=1;i<=n;i++)
    {
        TFO[i]=false;
        Dist[i]=-1;
    }

    myheapy.clear();

    helper.ver=1;
    helper.val=0;
    myheapy.push_back(helper);
    push_heap(myheapy.begin(),myheapy.end(),AwesomeCompare);

    for (i=1;i<=n;i++)
    {
        if (myheapy.size()==0)
        {
            break;
        }

        do
        {
            mytop=myheapy.front();
            pop_heap(myheapy.begin(),myheapy.end(),AwesomeCompare);
            myheapy.pop_back();
        }while(TFO[mytop.ver] && myheapy.size()!=0);

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

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

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

            myheapy.push_back(helper);
            push_heap(myheapy.begin(),myheapy.end(),AwesomeCompare);
        }
    }

    return;
}

int main()
{
    Int i,j;
    Int a,b,c,cm;
    gr helper;
    Int amount=0;

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

    for (i=1;i<=m;i++)
    {
        if (amount>5000000)
        {
            cout<<"NOPE"<<endl;
            return 0;
        }
        scanf("%lld %lld %lld %lld",&cm,&a,&b,&c);

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

                    Graph[b].push_back(helper);
                }
            }
            else
            {
                if (c>=0)
                {
                    continue;
                }

                for (j=0;j<Graph[a].size();j++)
                {
                    Graph[a][j].val+=c;
                }
            }
        }
    }

    Djikstra();

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

    return 0;
}
