/*
4 3
1 1 2 10
2 1 3 -9
1 1 3 8


4 4
1 1 2 10
2 1 3 -9
1 1 3 8
1 1 4 1


1000 4
1 1 2 10
2 1 3 -9
1 1 3 8
1 1 4 1


10000 32
1 1 2 10
2 1 3 -9
1 1 3 8
1 1 4 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1
2 1 2 1
2 2 1 1

10000 1
1 1 2 10
*/

#include <cstdio>
#include <iostream>

using namespace std;

#define MAXN 100000
#define MAXM 100000
#define MAXE 1000000

long long INF=999999999;

#define END -1

/*
struct tail { int ar[MAXN],n; tail(); void add(int); int pop(); } q;
tail :: tail() { n=0; }
void tail :: add(int val) { ar[n]=val; n++; }
int tail :: pop() { n--; return ar[n]; }
*/

int to[MAXE],first[MAXN],next[MAXE],E=0;
long long w[MAXE];
bool FAIL=false;
inline void add_edge(int a, int b, long long weight)
{
	for(int i=first[a]; i!=END; i=next[i]) if(to[i]==b) { if(w[i]<weight) w[i]=weight; return; }
	if(E==MAXE) {FAIL=true; return;} to[E]=b; next[E]=first[a]; first[a]=E; w[E]=weight; E++;
}

int N,M;

void ready() { scanf("%d%d", &N, &M); for(int i=0; i<N; i++) first[i]=END; }
void set()
{
	INF *= INF;
	int cmd,a,b,c;
	for(int i=0; i<M; i++)
	{
		scanf("%d%d%d%d", &cmd,&a,&b,&c);
		a--; b--;
		if(cmd==1) add_edge(a,b,(long long)c);
		else for(int i=first[a]; i!=END; i=next[i]) add_edge(b, to[i], w[i]+(long long)c);
	}
	
}
bool v[MAXN];
bool u[MAXN];
long long sol[MAXN];
void go()
{
	long long m;
	int j0;
	for(int i=0; i<N; i++) sol[i]=-1;
	v[0]=true; sol[0]=0;
	do
	{
		m=INF;
		for(int i=0; i<N; i++)
			if(v[i] and !u[i])
			{
				//printf("---%d\n", i);
				u[i]=true;
				for(int j=first[i]; j!=END; j=next[j])
				{
					if(!v[to[j]])
					{
						u[i]=false;
						if(sol[i]+w[j]<m )
						{
							//printf("-----%d(%d)\n", to[j],sol[i]+w[j]);
							m = sol[i]+w[j];
							j0 = to[j];
						}
					}
				}
			}
		if(m<INF)
		{
			v[j0]=true;
			sol[j0]=m;
			//printf("%d %d\n",j0,m);
		}
		//printf("-1\n");
	} while(m<INF);
}
//	int t;

int main()
{
	//scanf("%lld", &t);
	//cin >> t;
	//cout << t << "\n";
	ready();
	set();
	go();
	//sol[1] = sol[1]*sol[1]*sol[1]*999999999;
	//for(int i=1; i<N; i++) cout << sol[i] << "\n";
	for(int i=1; i<N; i++) printf("%lld\n", sol[i]);
	//printf("%d\n", E);
	/*
	for(int i=0; i<N; i++)
	{
		printf("%d: ", i);
		for(int j=first[i]; j!=END; j=next[j]) printf("%d(%lld) ", to[j], w[j]);
		printf("\n");
	}
	*/
	
	return 0;
}
