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

#include <cstdio>
#include <iostream>

using namespace std;

#define MAXN 100000
#define MAXM 100000
#define MAXE 10000000

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) { 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", &cmd,&a,&b); cin>>c;
		a--; b--;
		if(cmd==1) add_edge(a,b,c);
		else for(int i=first[a]; i!=END; i=next[i]) add_edge(b, to[i], w[i]+c);
	}
	
}
bool v[MAXN],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 main()
{
	ready();
	set();
	go();
	for(int i=1; i<N; i++) printf("%d\n", sol[i]);
	/*
	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;
}
