#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;

long long MAX;

struct edge
{
    long long t, val;
    int fict, num;
    edge(){}
    edge(long long _t, long long _val, int _fict, int _num)
    {
        t=_t;
        val=_val;
        fict=_fict;
        num=_num;
    }
    bool operator<(const edge &other)
    const{
        return val>other.val;
    }
};

long long n,m;
vector<edge> g[150000];
priority_queue<edge> q;
long long d[150000];
bool used[150000];

void init()
{
    MAX=1000000000000000LL;
    for(int i=0; i<=n+100; i++) d[i]=MAX;
}

void dijkstra()
{
    d[1]=0;
    q.push(edge(1,0,0,-1));

    edge cr;
    long long crt, crv, crf, crn;
    long long nt, nv, nf, nn;

    while(!q.empty())
    {
        cr=q.top();
        crt=cr.t; crv=cr.val; crf=cr.fict; crn=cr.num;
        q.pop();

        //cout << crt << ' ' <<crv << ' ' << crf << ' ' << crn << endl;

        //if the last edge was fictional go only to not fictional edges because they are not negative
        if(crf==1)
        {
            for(int i=0; i<g[crt].size(); i++)
            {
                nt=g[crt][i].t; nf=g[crt][i].fict;
                nv=crv+g[crt][i].val; nn=g[crt][i].num;

                if(!used[nt] && !nf && nn<crn && nv<d[nt])
                {
                    q.push(edge(nt,nv,0,nn));
                }
            }
        }
        else
        {
            if(used[crt]) continue;
            used[crt]=1;
            d[crt]=crv;
            //cout << "here " << g[crt].size() << "\n";
            for(int i=0; i<g[crt].size(); i++)
            {
                nt=g[crt][i].t; nf=g[crt][i].fict;
                nv=crv+g[crt][i].val; nn=g[crt][i].num;
                //cout << "------>" << nt << ' ' << nv << ' ' <<nf << ' ' << nn << endl;
                if(nf)
                {
                    q.push(edge(nt,nv,1,nn));
                }
                else if(!used[nt] && nv<d[nt])
                {
                    d[nt]=nv;
                    q.push(edge(nt,nv,0,nn));
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    long long a,b,c;
    int cmd;
    for(int i=0; i<m; i++)
    {
        //cin >> cmd;
        //cin >> a >> b >> c;
        scanf("%d", &cmd);
        cin >> a >> b >> c;
        //scanf("%lld%lld%lld", &a, &b, &c);
        //cout << cmd << ' ' << a << ' ' <<b << ' ' << c << endl;
        if(cmd==1)
        {
            //cout << a << " has an edge inserted in\n";
            g[a].push_back(edge(b,c,0,i));
        }
        else
        {
            //if(n<=2000 && m<=4000)
            //{
                for(int j=0; j<g[a].size(); j++) g[b].push_back(edge(g[a][j].t,g[a][j].val+c,0,i));
            //}
            //else g[b].push_back(edge(a,c,1,i));
        }
    }
    init();
    dijkstra();

    for(int i=2; i<=n; i++){
        if(d[i]==MAX) d[i]=-1;
        //cout << d[i] << endl;
        cout << d[i] << endl;
        //printf("%lld\n", d[i]);
    }

}

