Drunkard's Journey Home
Mathematica, 72 bytes

{1}//.{r___,x_}:&gt;{r,x,n=1;Check[RandomChoice[#[[x]]-&gt;(n++&amp;/@#)],##&amp;[]]}&amp;


This is a function takes the matrix as an argument and returns a list, and it uses 1-indexing.

The basic idea is to start with

{1}//.


which repeatedly applies the rule that follows to the list {1} until it stops changing. The rule matches the pattern

{r___,x_}:&gt;


which means "a list with zero or more elements called r followed by an element called x." This gives x as the last element in the current list, and we replace the list with

{r,x,&lt;stuff&gt;}


which is the original list with &lt;stuff&gt; appended. The stuff in question is

RandomChoice[#[[x]]-&gt;(n++&amp;/@#)]


which takes #[[x]] (the xth element of the input matrix) as a list of weights and maps them to n++&amp;/@#, which is short for Range@Length@# (i.e. {1,2,3,...} with the appropriate length). This will throw an error if the weights are all zero, which is why it's wrapped in a

Check[...,##&amp;[]]


which will return ##&amp;[] if an error message is generated. This is just a fancy way of writing Sequence[], which acts as a "nothing" element ({1,2,Sequence[],3} evaluates to {1,2,3}) and therefore leaves the list unchanged, causing the //. to stop replacing.