I just did some reading to see if I could find the answer and I keep coming across things like this
"After a general election, by convention, the leader of the party with the largest number of elected representatives will normally form the Government. The Governor General will ask the leader of that party to be the Prime Minister. He or she must be able at all times to maintain the confidence of the House in order to remain in power."
My understanding is what you had -- that the previous government gets the first kick at the can but this contradicts it. There seems to be a lot of cause for Canadians to be confused over who gets to try for Confidence first.