#include<fstream>
#include<set>
#define DIM 200004
using namespace std;
long long d[DIM],prof[DIM];
int sol[DIM],n,m;
struct nod{
	int info,nr;
	long long cost;
	long long pro;
	nod *next;};
nod *G[DIM];	
multiset< pair<long long, int> >T;
void adauga(int a,int b,int c,int d,int h);
void solve();
int main()
{
	ifstream fin("lazy.in");
	ofstream fout("lazy.out");
	fin>>n>>m;
	int i,a,b,c,e;
	for(i=1;i<=n;i++)
	{
		fin>>a>>b>>c>>e;
		adauga(a,b,c,c*e,i);
		adauga(b,a,c,c*e,i);
	}
	solve();
	for(i=2;i<=n;i++)
	   fout<<sol[i]<<" "<<"\n";
	return 0;
}
void adauga(int a,int b,int c,int d,int h)
{
	nod *p=new nod;
	p->info=b;
	p->nr=h;
	p->cost=c;
	p->pro=d;
	p->next=G[a];
	G[a]=p;
}
void solve()
{
	int i;
	for(i=1;i<=n;i++)
	   d[i]=1723783278379999992ll;
	d[1]=0;
	T.insert(make_pair(0,1));
	while(T.size())
	{
		int k=(*T.begin()).second;
		T.erase(T.begin());
		for(nod *p=G[k];p;p=p->next)
		   if(d[p->info]>p->cost)
		     T.insert(make_pair(p->cost,p->info)),d[p->info]=p->cost,sol[p->info]=p->nr,prof[p->info]=p->pro;
		   else
		     if(d[p->info]==p->cost)
		        if(prof[p->info]<p->pro)
		           prof[p->info]=p->pro,sol[p->info]=p->nr;
	 }
}