#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
int n,m,x,y,t,type,p,q,s,dist[100001],used[100001];
priority_queue < pair <int, int> > heap;
vector < pair <int, int> > v[100001];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&type,&x,&y,&t);
        if (type==1) {v[x].push_back(make_pair(t,y));continue;}
        s=v[x].size();
        for(int j=0;j<s;j++)
        {
            p=v[x][j].second;
            q=v[x][j].first;
            v[y].push_back(make_pair(t+q,p));
        }
    }
    for(int i=2;i<=n;i++)
       dist[i]=1000001;
    heap.push(make_pair(0,1));
    while(!heap.empty())
    {
        x=heap.top().second;
        heap.pop();
        used[x]=1;
        s=v[x].size();
        for(int i=0;i<s;i++)
        {
            y=v[x][i].second;
            t=v[x][i].first;
            dist[y]=min(dist[y],dist[x]+t);
            if (used[y]==0) {heap.push(make_pair(-dist[x]-t,y));}
        }
    }
    for(int i=2;i<=n;i++)
        if (dist[i]==1000001) printf("-1\n");
        else printf("%d\n",dist[i]);
	return 0;
}
/*
4 3
1 1 2 10
2 1 3 -9
1 1 3 8
*/
