#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define MAX 2000000001
using namespace std;
long long n,m,dist[100001],used[100001],t,a,b,c;
priority_queue<pair<long long, long long> > q;
vector<pair<long long, long long> > z[100001];
void dijkstra(long long s)
{
	for(int i=1; i<=n; i++)
	{
		dist[i]=MAX;
		used[i]=0;
	}
	dist[s]=0;
	q.push(make_pair(0,s));
	while(1)
	{
		if(q.empty()) break;
		int x=q.top().second;
		q.pop();
		while(used[x]==1&&!q.empty()) {x=q.top().second; q.pop();}
		if(q.empty()&&used[x]==1) break;
		used[x]=1;
		int p=z[x].size();
		for(int i=0; i<=p-1; i++)
		{
			int y=z[x][i].first;
			int t=z[x][i].second;
			if(dist[y]>dist[x]+t)
			{
				dist[y]=dist[x]+t;
				q.push(make_pair(-dist[y],y));
			}
		}
	}
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=m; i++)
	{
		scanf("%lld%lld%lld%lld",&t,&a,&b,&c);
		if(t==1&&a!=b)
			z[a].push_back(make_pair(b,c));
		else if(t==2)
		{
			int p=z[a].size();
			for(int j=0; j<=p-1; j++)
			{
				if(b==z[a][j].first) continue;
				else z[b].push_back(make_pair(z[a][j].first,z[a][j].second+c));
			}
		}
	}
	dijkstra(1);
	for(int i=2; i<=n; i++)
	{
		if(dist[i]==MAX) printf("-1\n");
		else printf("%lld\n",dist[i]);
	}
	return 0;
}
