import java.io.*;
import java.util.*;

public class MGPathfinder
{
	static int vertices,vstart,vend,histlen;
	static ArrayList[] adjlist; // array of arraylist of edges
	static String datafile = "dv2.in";
	
	public static void main(String args[]) throws IOException
	{	
		BufferedReader f = new BufferedReader(new FileReader(datafile));
		StringTokenizer st = new StringTokenizer(f.readLine());
		vertices = Integer.parseInt(st.nextToken());
		int edges = Integer.parseInt(st.nextToken());
		vstart = Integer.parseInt(st.nextToken());
		vend = Integer.parseInt(st.nextToken());
		histlen = Integer.parseInt(st.nextToken());
		adjlist = new ArrayList[vertices];
		for(int n=0; n<vertices; n++) adjlist[n] = new ArrayList();
		
		for(int n=0; n<edges; n++)
		{
			st = new StringTokenizer(f.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			boolean on = Integer.parseInt(st.nextToken())!=0;
			if(v1==v2) continue;
			Edge e = new Edge(v1,v2,on);
			adjlist[v1].add(e);
			adjlist[v2].add(e);	
			
			History h = e.getHistory();
			boolean h1;
			boolean h2=on;
			for(int i=0; i<histlen; i++)
			{
				h1 = Integer.parseInt(f.readLine())!=0;
				h.addEntry(h1,h2);
				h2=h1;
			}
		}

		int curvertex = vstart;
		int totaltime = 0;
		while(curvertex!=vend)
		{
			System.out.println(curvertex);
			Edge next = alg(curvertex);
			System.out.println(next.getVertex(-1)+"    "+next.getVertex(next.getVertex(-1)));
			totaltime++;
			curvertex = next.getVertex(curvertex);
			evolve();
		}
		
		System.out.println(totaltime);
		System.exit(0);
	}
	public static void evolve()
	{
		for(int v=0; v<vertices; v++)
			for(int e=0; e<adjlist[v].size(); e++)
			{
				Edge E = (Edge)adjlist[v].get(e);
				E.setOn(evolfunc( E.getOn() ));
			}
	}
	public static boolean evolfunc(boolean on)
	{
		if(Math.random()<0.25) return !on;
		return on;
	}
	public static Edge alg(int curvertex)
	{
		int tlimit = 10;
		double[] curvals = new double[vertices];
		double[] prevvals = new double[vertices];
		Edge[][] bestprev = new Edge[vertices][tlimit];
		int bestendtime = -1;
		double bestend = -1;
		double inf = Double.MAX_VALUE/5;
		for(int v=0; v<vertices; v++) prevvals[v] = inf;
		prevvals[curvertex] = 0;
		for(int t=0; t<tlimit; t++)
		{
			for(int v=0; v<vertices; v++)
			{
				curvals[v] = inf;
				for(int e=0; e<adjlist[v].size(); e++)
				{
					Edge E = (Edge)adjlist[v].get(e);
					if(prevvals[E.getVertex(v)]>=inf) continue;
					double x = 0;//globhist.predictMutations(E.getWeight(),t) + prevvals[E.getVertex(v)];
					if(x<curvals[v])
					{
						curvals[v] = x;
						bestprev[v][t] = E;
					}
				}
			}
			for(int v=0; v<vertices; v++)
				prevvals[v] = curvals[v];
			if(curvals[vend]<inf)
			{
				if(curvals[vend]<bestend||bestend<0)
				{
					bestendtime = t;
					bestend = curvals[vend];
				}
			}
			else if(t==tlimit-1) System.out.println("Time limit is insufficient for the width of this graph");
		}			
		int btrack = vend;
		for(int t=bestendtime; t>0; t--)
		{
			System.out.println(t + " " + btrack);
			btrack = bestprev[btrack][t].getVertex(btrack);
		}
		return bestprev[btrack][0];
	}
}

class Edge
{
	int ev1;
	int ev2;
	boolean eon;
	boolean evolved;
	History ehist;
	
	public Edge(int v1, int v2, boolean on)
	{
		ev1=v1; ev2=v2; eon=on; evolved=false; ehist = new History();
	}
	public void setOn(boolean on)
	{ 
		evolved=!evolved; //The evolution loop will hit each edge twice, so we have to negate one of the evolutions.
		if(evolved) eon=on;
	}
	public boolean getOn()
	{
		return eon;
	}
	public int getVertex(int a)
	{
		if(a==ev1) return ev2;
		if(a==ev2) return ev1;
		return Math.min(ev1,ev2);
	}
	public History getHistory()
	{
		return ehist;
	}
}

class History
{
	int ontooff, offtoon, ontoon, offtooff;
	
	public History()
	{
		ontooff=0; offtoon=0; ontoon=0; offtooff=0;
	}
	public void addEntry(boolean b1, boolean b2)
	{
		if(b1&&b2) ontoon++;
		if(b1&&!b2) ontooff++;
		if(!b1&&b2) offtoon++;
		if(!b1&&!b2) offtooff++;
	}
	public double getChangeProb(boolean cur)
	{
		if(cur) return (double)ontooff/(ontoon+ontooff);
		return (double) offtoon/(offtooff+offtoon);
	}
}