#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];
vector<Int> HGraph[100001];
Int n,m;
bool TFO[100001];
Int Dist[100001];
vector<gr> myheapy;
Int edges[2001][2001];

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;
    }

    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);

    if (n>2000)
    {
        for (i=1;i<=m;i++)
        {
            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;
                    }
                }
            }
        }
    }
    else
    {
        for (i=0;i<=2000;i++)
        {
            for (j=0;j<=2000;j++)
            {
                edges[i][j]=0;
            }
        }
        for (i=1;i<=m;i++)
        {
            scanf("%lld %lld %lld %lld",&cm,&a,&b,&c);

            if (cm==1)
            {
                if (edges[a][b]==0)
                {
                    edges[a][b]=c;
                    HGraph[a].push_back(b);
                }
                else if (edges[a][b]>c)
                {
                    edges[a][b]=c;
                }
            }
            else
            {
                if (a==b)
                {
                    if (c>=0)
                    {
                        continue;
                    }

                    for (j=0;j<HGraph[a].size();j++)
                    {
                        edges[a][ HGraph[a][j] ]+=c;
                    }
                }
                else
                {
                    for (j=0;j<HGraph[a].size();j++)
                    {
                        if (edges[b][ HGraph[a][j] ]==0)
                        {
                            edges[b][ HGraph[a][j] ]=c+edges[a][ HGraph[a][j] ];
                            HGraph[b].push_back(HGraph[a][j]);
                        }
                        else if (edges[b][ HGraph[a][j] ]>c+edges[a][ HGraph[a][j] ])
                        {
                            edges[b][ HGraph[a][j] ]=c+edges[a][ HGraph[a][j] ];
                        }
                    }
                }
            }
        }

        for (i=1;i<=n;i++)
        {
            for (j=0;j<HGraph[i].size();j++)
            {
                helper.ver=HGraph[i][j];
                helper.val=edges[i][ HGraph[i][j] ];
                Graph[i].push_back(helper);
            }
        }
    }

    Djikstra();

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

    return 0;
}
