#include<iostream>
#include<fstream>

using namespace std;

struct Element
{
	int key;
	Element* Next;
	Element* Previous;
};

class Queue
{
public:
	int Count;
	Element* First;
	Element* Last;
	Queue();
	~Queue();
	bool Add(int key);
	bool Empty();
	int Delete();
};

int Min(int a, int b);

//класс Queue

Queue::Queue()
{
	First = 0;
	Last = 0;
	Count = 0;
}

Queue::~Queue()
{
	int k;
	while (!Empty())
		k = Delete();
}

bool Queue::Empty()
{
	if (Count)
		return 0;
	return 1;
}

bool Queue::Add(int key)
{
	Element* a;
	a = new Element;
	a->key = key;
	a->Previous = Last;
	a->Next = 0;
	if (Last)
		Last->Next = a;
	Last = a;
	if (!First)
		First = a;
	Count++;
	return 1;
}

int Queue::Delete()
{
	if (Count)
	{
		int k = First->key;
		if (Count == 1)
			delete First;
		else
		{
			First = First->Next;
			delete First->Previous;
		}
		Count--;
		return k;
	}
	return 1;
}

int Min(int a, int b)
{
	if (a > b)
		return b;
	return a;
}

struct Duga
{
	int begin;
	int end;
	int length;
	int width;
};

struct Node
{
	int key;
	int length;
	int width;
	int parent;
};


int main()
{
	ifstream in;
	in.open("Graf.txt");
	int Count, NCount;
	in >> NCount >> Count;
	Duga *mas;
	mas = new Duga[Count];
	Node *array;
	array = new Node[NCount];
	for (int j = 0; j < NCount; j++)
	{
		in >> array[j].key;
		array[j].length = 0;
		array[j].width = 0;
		array[j].parent = 0;
	}
	for (int i = 0; i < Count; i++)
	{
		in >> mas[i].begin >> mas[i].end >> mas[i].length >> mas[i].width;
	}
	cout << "Enter The Start Node: ";
	int Start, Finish;
	cin >> Start;
	cout << "Enter The Finish Node: ";


	cin >> Finish;
	Queue q;
	q.Add(Start);
	array[0].width = mas[1].width;
	while (!q.Empty())
	{
		int w = q.Delete();
		for (int i = 0; i < Count; i++)
		{
			if (mas[i].begin == w)
			{
				if (array[mas[i].end].length == 0)
				{
					array[mas[i].end].length = array[mas[i].begin].length + mas[i].length;
					if (mas[i].begin != Start)
						array[mas[i].end].width = Min(array[mas[i].begin].width, mas[i].width);
					else
						array[mas[i].end].width = mas[i].width;
					q.Add(mas[i].end);
					array[mas[i].end].parent = array[mas[i].begin].key;
				}
				else
					if (array[mas[i].end].length > array[mas[i].begin].length + mas[i].length)
					{
						array[mas[i].end].length = array[mas[i].begin].length + mas[i].length;
						array[mas[i].end].width = Min(array[mas[i].begin].width, mas[i].width);
						array[mas[i].end].parent = array[mas[i].begin].key;
					}
					else
						if ((array[mas[i].end].length == array[mas[i].begin].length + mas[i].length) && ((array[mas[i].begin].width > array[mas[i].end].width) || (array[mas[i].end].width == 0)))
						{
							array[mas[i].end].width = array[mas[i].begin].width;
							array[mas[i].end].parent = array[mas[i].begin].key;
						}

			}
		}
	}
	for (int i = 0; i < NCount; i++)
	{
		if (array[i].key == Finish)
			cout << array[i].length << " " << array[i].width << endl;
	}
	int Current = Finish;
	while (Current != Start)
	{
		cout << Current << "  ";
		Current = array[Current].parent;
	}
	cout << Current << endl;
	cout << "Press Any Key To Exit: ";
	cin >> Count;
	return 1;
}