Какие есть способы реализации случайной выборки с учетом веса?

Имеется список таплов, например
inp = [('a', 1), ('b', 3), ('c', 2)]
Как можно реализовать выборку случайного элемента, с учетом его веса?
Сейчас на ум приходит только 2 варианта

1. Прописать каждому элементу "промежуток", где длина = вес, т.е. что-то типо
   tmp = [('a', 0, 1), ('b', 2, 4), ('c', 5, 6)]
   генерировать случайное число [0, 6] и находить соответствие в списке
2. Сделать новый массив, где количество повторений каждого элемента = его весу, т.е.
   

   lst = []
   for elem, weight in inp:
       lst.extend([elem] * weight)

   
   И далее random.choice(lst)

Update: оптимальным вариантом оказался следующий способ:

1. подсчитываем сумму всех весов в переданном списке, обозначим ее weight_sum.
2. находим случайное число от 1 до weight_sum, запомним как rand_res
3. проходим по списку и вычитаем от rand_res вес текущего элемента. Там где rand_res <= 0 лежит искомый случайный элемент./li>
   

Этот способ при минимальной доработке хорошо работает если необходимо вернуть k случайных элементов. Работает за О(n*(k+1)) и требует О(k) памяти