In that case, this should work:
a = torch.Tensor([[3,4, -1, -1,5,6],
                  [-1,5,-1,1,-1,-1],
                  [-1,4,4,2,3,0]])

valid_idx = (a!=-1).nonzero()
choice = torch.multinomial(torch.arange(valid_idx.size(0)).float(), 1)
a[valid_idx[choice].squeeze().chunk(2)]

EDIT: Sorry, I didn’t realized you would like to sample from each line.
Will update the code in a minute.
EDIT2: I’m not sure, if we can avoid using a loop in this case:
valid_idx = (a!=-1).nonzero()
unique_rows = valid_idx[:, 0].unique()
valid_row_idx = [valid_idx[valid_idx[:, 0] == u] for u in unique_rows]

ret = []
for v in valid_row_idx:
    choice = torch.multinomial(torch.arange(v.size(0)).float(), 1)
    ret.append(a[v[choice].squeeze().chunk(2)])
ret = torch.stack(ret)