Clear[lexicallySort]
lexicallySort[lst : {{_?NumericQ ..} ..}] := lst //
            PadRight[#, {Length@#, Max[Length /@ #]}, Min[#] - 1] & //
        Sort[#] /. Evaluate[Min[lst] - 1] :> Sequence[] &

lexicallySort[{
               {1, 2, 1, 3, 1, 3, 1, 3},
               {1, 2, 1, 3, 1, 1, 1, 4},
               {1, 2, 1, 3},
               {1, 2, 1, 3, 1, 1},
               {1, 2, 1, 3, 1, 3, 1, 4},
               {1, 2, 1, 3, 1, 3},
               {1, 2, 1, 3, 1, 1, 1, 3},
               {1, 2},
               {1, 3}
              }] // Grid

1 2
1 2 1 3
1 2 1 3 1 1
1 2 1 3 1 1 1 3
1 2 1 3 1 1 1 4
1 2 1 3 1 3
1 2 1 3 1 3 1 3
1 2 1 3 1 3 1 4
1 3